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 .
Drawings
The drawings are objected to under 37 CFR 1.83(a) because they fail to show: Figure 16 with a label “efficient 3D mesh extraction engine 1620” and Figure 23 with a label of “read-only memory (ROM) 2320” as described in the specification. 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.
Specification
The disclosure is objected to because of the following informalities: paragraph 215 discloses a “read-only memory (ROM) 2320” and should be “read-only memory (ROM) 2318”. Appropriate correction is required.
The disclosure is objected to because of the following informalities: paragraph 76 discloses a “processor 2510 discussed with respect to the computing system 2500” the labels for 2510 and 2500 does not seem to exist within the figures. Appropriate correction is required.
The disclosure is objected to because of the following informalities: paragraph 77 discloses a “random access memory (RAM) 140/2520”; such indicated labeling needs to be either 140 or 2520. Unless applicant is referring to Figure 23 where (RAM) is labeled as 2325. Appropriate correction is required.
The disclosure is objected to because of the following informalities: paragraph 77 discloses a “read-only memory (ROM) 145/2525”; such indicated labeling needs to be either 145 or 2525. Unless applicant is referring to Figure 23 where (ROM) is labeled as 2318. Appropriate correction is required.
The disclosure is objected to because of the following informalities: paragraph 77 discloses a “cache 2512” where “cache 2512” does not exist and should be “cache 2312”. Appropriate correction is required.
The disclosure is objected to because of the following informalities: paragraph 77 discloses a “memory 2515” where “memory 2515” does not exist and should be “memory 2315”. Appropriate correction is required.
The disclosure is objected to because of the following informalities: paragraph 77 discloses a “another storage device 2530” where “another storage device 2530” does not exist and should be “Storage device 2330”. Appropriate correction is required.
The disclosure is objected to because of the following informalities: paragraph 77 discloses a “another storage device 2530” where “another storage device 2530” does not exist and should be “Storage device 2330”. Appropriate correction is required.
The disclosure is objected to because of the following informalities: paragraph 78 discloses a “any other output device 2530” where “any other output device 2530” does not exist and should be “output device 2335”. Appropriate correction is required.
The disclosure is objected to because of the following informalities: paragraph 78 discloses a “any other input device 2545” where “any other input device 2545” does not exist and should be “input device 2345”. Appropriate correction is required.
The disclosure is objected to because of the following informalities: paragraph 158 discloses a “efficient 3D mesh extraction engine 1620” where “efficient 3D mesh extraction engine 1620” does not exist in Figure. Appropriate correction is required.
The disclosure is objected to because of the following informalities: paragraph 159 discloses a “efficient 3D mesh extraction engine 1620” where “efficient 3D mesh extraction engine 1620” does not exist in Figure. Appropriate correction is required.
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-2, 4-6, 24-25, and 27-29 is/are rejected under 35 U.S.C. 103 as being unpatentable over Powers et al. (U.S. Pub. No. 20190318547) in view of Schoenberg (U.S. Pub. No. 20160364907) and Molyneaux et al. (U.S. Pub. No. 20190197774).
Regarding claim 1, Powers discloses an apparatus for three-dimensional (3D) reconstruction of a scene, the apparatus comprising (para 23, “This disclosure includes techniques and implementations for improved real-time capturing of a three-dimensional (3D) environment with respect to a spatial interaction system For example, a user may capture image data associated with a home or another physical environment using a mobile electronic device, for instance, a tablet, a smart phone, notebook computer, interactive headset, virtual reality system, or other image capture device.”; also, para 26, ‘In some examples, the system described herein, is configured to model a physical space as a 3D virtual environment using a collection of viewpoint bundles.”): at least one memory (para 128, “The mobile device 1800 may also include one or more processors 1812, such as at least one or more access components, control logic circuits, central processing units, or processors, as well as one or more computer-readable media 1814 to perform the function associated with the system 1802.”; also, CRM is considered to be a form of a memory); and at least one processor coupled to the at least one memory and configured to (para 129, “Several modules such as instruction, data stores, and so forth may be stored within the computer-readable media 1814 and configured to execute on the processors 1812.”): select a plurality of voxel blocks for the scene based on depth data and pose data indicative of a perspective of the depth data (para 37, “In some implementations, to enable combination and/or subtraction of viewpoint bundles, each viewpoint bundle may be represented as an unbounded TSDF volume. The unbounded TSDF volume may be partitioned into units called voxel blocks, each formed by a plurality of voxels. For example, the voxel block may be formed as a 4×4×4 volume of voxels. In the current example, each voxel block may be fused with a depth frame and allocated only when the corresponding physical space is observed (e.g., detected within a depth map of the physical environment).”; also, para 41, “In real-time applications, depth data is captured based on a current view and, thus, the system may limit updating and merging to the voxel blocks inside the viewing system to reduce processing time.”; also, para 38, “In some particular implementations, the size of a voxel block may vary based on the distance from the current pose of the mobile device.”; also, selecting voxel blocks by allocating them when corresponding physical space is observed within a depth frame and limiting updates to blocks inside of the current viewing system. Voxel boxes are linked to the current pose of the mobile device for updating and size variation); generate, based on at least one of the depth data or the pose data, a respective 3D representation value for each voxel block of the plurality of voxel blocks (para 30, “In one example, the system may update a tracking TSDF volume (e.g., the active or visible TSDF volume) by iterating over the pixels of each depth frame received and updating the corresponding voxel blocks of the TSDF volume with the depth data.”; also, para 26, “Each viewpoint may include depth image data represented as voxels, color image data, and a pose (e.g., position, orientation, and direction of view, etc.) of the mobile device at the time the image data was captured. In one example, the viewpoints may be accumulated together as a volume of voxels using a Truncated Signed Distance Function (TSDF) that accumulates information about the scene geometry over time (e.g., over viewpoints).”); voxel block of the plurality of voxel blocks (para 37, “The unbounded TSDF volume may be partitioned into units called voxel blocks, each formed by a plurality of voxels.”; also, para 30, “In one example, the system may update a tracking TSDF volume (e.g., the active or visible TSDF volume) by iterating over the pixels of each depth frame received and updating the corresponding voxel blocks of the TSDF volume with the depth data.”); identify one or more voxel blocks of the plurality of voxel blocks (para 39, “In this example, when scanning (e.g., capturing image data of the physical environment), the system may re-mesh the voxel blocks that underwent a TSDF update.”; also, para 41, “In real-time applications, depth data is captured based on a current view and, thus, the system may limit updating and merging to the voxel blocks inside the viewing system to reduce processing time.”) generate a 3D mesh based on the identified one or more voxel blocks (para 39, “For instance, each voxel block may be configured to store a sub-mesh which is determined from the voxel TSDF using a marching cubes technique. In this example, multiple sub-meshes (from multiple voxel blocks) are merged into a global mesh (e.g., the global mesh). In this example, when scanning (e.g., capturing image data of the physical environment), the system may re-mesh the voxel blocks that underwent a TSDF update.”); and compare each of the respective 3D representation values with a corresponding respective previous 3D representation value to estimate a distance difference, having a distance difference greater than a distance threshold, and generate a simplified 3D mesh based on the generated 3D mesh.
However, in a similar field of endeavor, Schoenberg discloses compare each of the respective 3D representation values with a corresponding respective previous 3D representation value to estimate a distance difference (para 54, “As new depth information is received, and updated signed distance field values are assigned, the updated signed distance field values are compared to the previous signed distance field values for each voxel.”; also, para 54, “For each subset, if the sum of the value differences for each voxel within the subset is greater than a threshold, Marching Cubes may be executed on the subset.”), and having a distance difference greater than a distance threshold (para 54, “For each subset, if the sum of the value differences for each voxel within the subset is greater than a threshold, Marching Cubes may be executed on the subset.”; also, para 54, “If the sum is less than the threshold, the mesh reconstruction for that subset is preserved from the previous iteration.”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Powers's invention of an apparatus for three-dimensional reconstruction of a scene having at least one memory and at least one processor coupled to the at least one memory that selects a plurality of voxel blocks for the scene based on depth data and pose data indicative of a perspective of the depth data, generates a respective three-dimensional representation value for each voxel block of the plurality of voxel blocks, identifies one or more voxel blocks of the plurality of voxel blocks, and generates a three-dimensional mesh based on the identified one or more voxel blocks, with the features of Schoenberg's invention of comparing each of the respective three-dimensional representation values with a corresponding respective previous three-dimensional representation value to estimate a distance difference and of a distance difference greater than a distance threshold. The combination would have been obvious because Powers already re-meshes only the voxel blocks that underwent a truncated signed distance function update and expressly limits its updating and merging in order to reduce processing time, yet Powers never states how a block is judged to have changed, and Schoenberg supplies exactly that test by comparing the updated signed distance field values against the previous signed distance field values for each voxel and by gating whether the mesh is regenerated on whether the summed value differences for a subset of voxels exceed a threshold, so a person of ordinary skill working on Powers's block-based reconstruction and pursuing the reduction in processing time that Powers itself identifies would have looked to Schoenberg, which states its own purpose as computational and power savings obtained by not regenerating mesh that is substantially similar to the previous mesh. Both references hold signed distance values on a voxel grid and both extract mesh by marching cubes, so Schoenberg's test reads the very values Powers already stores and its outcome feeds the marching cubes step Powers already performs, and the result is a reconstruction in which meshing is confined to the blocks whose stored distance values actually changed by more than the threshold, so that unchanged geometry is not re-meshed and the processing time Powers is expressly trying to limit falls.
Molyneaux discloses generate a simplified 3D mesh based on the generated 3D mesh (para 208, “A mesh, for example, may be simplified by reducing the number of such polygons in the mesh. As a specific example, the first simplification operation may employ a triangle reduction algorithm, which may reduce the number of triangles used to represent the XR environment.”; also, para 228, “At act 3012, a pre-simplification operation may be performed on a selected first mesh block to generate a second mesh block. The pre-simplification operation may reduce the complexity of the block. For a mesh block, the pre-simplification may reduce the number of polygons in the mesh block.”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further modified Powers in view of Schoenberg, in which the apparatus accumulates depth and pose data into a plurality of voxel blocks, compares each voxel block's current three-dimensional representation value against the corresponding previous value to estimate a distance difference, identifies the voxel blocks whose distance difference exceeds a distance threshold, and generates a three-dimensional mesh from the identified voxel blocks, with the features of Molyneaux's invention of generating a simplified three-dimensional mesh based on the generated three-dimensional mesh. The combination would have been obvious because the base combination produces a global mesh assembled from the sub-meshes of many voxel blocks and says nothing about reducing the size of that mesh once it is built, while Molyneaux supplies precisely that missing step by teaching a simplification operation that reduces the number of polygons used to represent an environment, and a person of ordinary skill building a mesh of a physical environment for interactive display on the mobile device Powers describes would have looked to Molyneaux because Molyneaux addresses the same problem of holding and rendering a mesh of a scanned environment within the limited memory and rendering budget of such a device. Molyneaux's simplification takes an already generated mesh as its input and returns a mesh of the same form, so it follows the base combination's mesh generation without disturbing the way that mesh is assembled from the sub-meshes of the changed voxel blocks, and it yields a mesh carrying the same scanned surface with fewer polygons and therefore a lower memory and rendering cost on the mobile devices Powers targets, which is the same economy Powers is already pursuing when it confines its updating and merging to the voxel blocks inside the current view.
Regarding claim 2, Powers as modified by Schoenberg and Molyneaux discloses the apparatus of claim 1, wherein Powers further discloses the respective 3D representation values are truncated signed distance function (TSDF) values or point cloud values (para 40, “Further, since each edge index encodes two end points, the system may determine the TSDF values of the two voxel end points and then update the associated vertex position without calculating the faces, as is discussed in more detail below.”; also, para 26, “In one example, the viewpoints may be accumulated together as a volume of voxels using a Truncated Signed Distance Function (TSDF) that accumulates information about the scene geometry over time (e.g., over viewpoints).”; also, para 37, “The unbounded TSDF volume may be partitioned into units called voxel blocks, each formed by a plurality of voxels.”).
Regarding claim 4, Powers as modified by Schoenberg and Molyneaux discloses the apparatus of claim 1, wherein Powers further discloses the at least one processor is configured to generate the 3D mesh based on a marching cube algorithm (para 39, “For instance, each voxel block may be configured to store a sub-mesh which is determined from the voxel TSDF using a marching cubes technique.”; also, para 40, “In the current example, the system may perform marching cubes using the voxel blocks by creating a vertex on an edge between two adjacent voxels (with different signs), either in x, y or z direction.”).
Regarding claim 5, Powers as modified by Schoenberg and Molyneaux discloses the apparatus of claim 1, wherein Molyneaux further discloses, to generate the simplified 3D mesh, the at least one processor is configured to fuse one or more triangles together within the generated 3D mesh (para 192, “For example, plane detection 1404 may compare primitive normals of each mesh triangle in a sub-brick; merge those mesh triangles, with primitive normal differences smaller than a predetermined threshold value, into one mesh triangle; and identify a mesh triangle with an area larger than a predetermined area value as a plane.”; also, para 190, “Mesh bricks 1308 may be extracted from the SDFs 1306 by, for example, applying a marching cube algorithm over corresponding bricks”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further modified Powers in view of Schoenberg, in which the apparatus detects the voxel blocks whose three-dimensional representation values changed by more than a distance threshold and generates a three-dimensional mesh from those blocks, with the features of Molyneaux's invention of generating the simplified three-dimensional mesh by fusing one or more triangles together within the generated three-dimensional mesh. The combination would have been obvious because the base combination merges the sub meshes stored in its voxel blocks into a single global mesh whose triangle count grows with the size of the scanned environment and provides no mechanism for combining neighbouring triangles once they are produced. Molyneaux supplies that mechanism for a mesh of exactly the same kind, one extracted from a signed distance field by a marching cube algorithm, teaching that the primitive normals of each mesh triangle are compared and that those triangles whose normals differ by less than a predetermined threshold are merged into one mesh triangle, so triangles lying on a common surface are joined into a single larger triangle rather than being individually retained. A person of ordinary skill confronting the growing triangle count of the global mesh of the base combination on the mobile device it runs on would have looked to Molyneaux, which treats the same problem of representing a scanned environment with fewer primitives, and applying the merge to the mesh the base combination already produces yields a mesh carrying the same scene surface with fewer triangles and a correspondingly lower memory and rendering cost.
Regarding claim 6, Powers as modified by Schoenberg and Molyneaux discloses the apparatus of claim 5, wherein Molyneaux further discloses, to generate the simplified 3D mesh, the at least one processor is further configured to minimize a number of triangles used for the simplified 3D mesh (para 210, “A second simplification operation that follows the region-based operation may further simplify the representation of the environment, such as by further reducing the number of polygons in the representation. The second simplification operation may focus on reducing the number of polygons within each region detected by the region-based operation.”; also, para 229, “For example, processing in act 3014 may require a minimum number of triangles and a target value provided by an application may be replaced by that minimum value if the target value is below the minimum number of triangles.”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further modified Powers in view of Schoenberg, in which the apparatus detects the voxel blocks whose three-dimensional representation values changed by more than a distance threshold and generates a three-dimensional mesh from those blocks, with the features of Molyneaux's invention of minimizing a number of triangles used for the simplified three-dimensional mesh. The combination would have been obvious because the base combination already merges the mesh triangles lying on a common surface into one mesh triangle, which is the region-based operation of Molyneaux, and having done so it stops, leaving whatever triangle count that merge happens to produce. Molyneaux teaches the stage that comes next, a second simplification operation that follows the region-based operation and further simplifies the representation by further reducing the number of polygons within each region the region-based operation detected, and teaches that the reduction is driven toward a target value bounded below by a minimum number of triangles so that it is carried as far as the downstream processing permits. A person of ordinary skill who had merged the coplanar triangles of the base combination would have looked to Molyneaux for that following stage, because Molyneaux places the two operations in that order in one pipeline and describes the second as operating on the regions the first produced, and applying it drives the triangle count of the simplified mesh down to the smallest number that still represents the scanned surface, which conserves the memory and rendering budget of the mobile device the base combination runs on.
Regarding claim 24, Powers discloses a method for three-dimensional (3D) reconstruction of a scene, the method comprising (para 95, “FIG. 12 is an example flow diagram showing an illustrative process 1200 for associating image data with a viewpoint bundle according to some implementations. As discussed above, in some implementations, the system is configured to model a physical space as a 3D virtual environment using a collection of viewpoint bundles.”; also, para 94, “The order in which the operations are described should not be construed as a limitation. Any number of the described blocks can be combined in any order and/or in parallel to implement the process, or alternative processes, and not all of the blocks need be executed.”; also, para 96, At 1202, the system may receive image data of a physical environment from a device.”): selecting a plurality of voxel blocks for the scene based on depth data and pose data indicative of a perspective of the depth data (para 37, “In some implementations, to enable combination and/or subtraction of viewpoint bundles, each viewpoint bundle may be represented as an unbounded TSDF volume. The unbounded TSDF volume may be partitioned into units called voxel blocks, each formed by a plurality of voxels. For example, the voxel block may be formed as a 4×4×4 volume of voxels. In the current example, each voxel block may be fused with a depth frame and allocated only when the corresponding physical space is observed (e.g., detected within a depth map of the physical environment).”; also, para 41, “In real-time applications, depth data is captured based on a current view and, thus, the system may limit updating and merging to the voxel blocks inside the viewing system to reduce processing time.”; also, para 38, “In some particular implementations, the size of a voxel block may vary based on the distance from the current pose of the mobile device.”; also, selecting voxel blocks by allocating them when corresponding physical space is observed within a depth frame and limiting updates to blocks inside of the current viewing system. Voxel boxes are linked to the current pose of the mobile device for updating and size variation); generating, based on at least one of the depth data or the pose data, a respective 3D representation value for each voxel block of the plurality of voxel blocks (para 30, “In one example, the system may update a tracking TSDF volume (e.g., the active or visible TSDF volume) by iterating over the pixels of each depth frame received and updating the corresponding voxel blocks of the TSDF volume with the depth data.”; also, para 26, “Each viewpoint may include depth image data represented as voxels, color image data, and a pose (e.g., position, orientation, and direction of view, etc.) of the mobile device at the time the image data was captured. In one example, the viewpoints may be accumulated together as a volume of voxels using a Truncated Signed Distance Function (TSDF) that accumulates information about the scene geometry over time (e.g., over viewpoints).”); each voxel block of the plurality of voxel blocks (para 37, “The unbounded TSDF volume may be partitioned into units called voxel blocks, each formed by a plurality of voxels.”; also, para 30, “In one example, the system may update a tracking TSDF volume (e.g., the active or visible TSDF volume) by iterating over the pixels of each depth frame received and updating the corresponding voxel blocks of the TSDF volume with the depth data.”); identifying one or more voxel blocks of the plurality of voxel blocks (para 39, “In this example, when scanning (e.g., capturing image data of the physical environment), the system may re-mesh the voxel blocks that underwent a TSDF update.“; also, para 41, “In real-time applications, depth data is captured based on a current view and, thus, the system may limit updating and merging to the voxel blocks inside the viewing system to reduce processing time.“) generating a 3D mesh based on the identified one or more voxel blocks (para 39, “For instance, each voxel block may be configured to store a sub-mesh which is determined from the voxel TSDF using a marching cubes technique. In this example, multiple sub-meshes (from multiple voxel blocks) are merged into a global mesh (e.g., the global mesh). In this example, when scanning (e.g., capturing image data of the physical environment), the system may re-mesh the voxel blocks that underwent a TSDF update.”); and . Powers does not disclose comparing each of the respective 3D representation values with a corresponding respective previous 3D representation value to estimate a distance difference, having a distance difference greater than a distance threshold and generating a simplified 3D mesh based on the generated 3D mesh.
However, in a similar field of endeavor, Schoenberg discloses comparing each of the respective 3D representation values with a corresponding respective previous 3D representation value to estimate a distance difference (para 54, “As new depth information is received, and updated signed distance field values are assigned, the updated signed distance field values are compared to the previous signed distance field values for each voxel.”; also, para 54, “For each subset, if the sum of the value differences for each voxel within the subset is greater than a threshold, Marching Cubes may be executed on the subset.”), having a distance difference greater than a distance threshold (para 54, “For each subset, if the sum of the value differences for each voxel within the subset is greater than a threshold, Marching Cubes may be executed on the subset.”; also, para 54, “If the sum is less than the threshold, the mesh reconstruction for that subset is preserved from the previous iteration.”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Powers's invention of a method for three-dimensional reconstruction of a scene in which a plurality of voxel blocks is selected for the scene based on depth data and pose data indicative of a perspective of the depth data, a respective three-dimensional representation value is generated for each voxel block of the plurality of voxel blocks, one or more voxel blocks of the plurality of voxel blocks are identified, and a three-dimensional mesh is generated based on the identified one or more voxel blocks, with the features of Schoenberg's invention of comparing each of the respective three-dimensional representation values with a corresponding respective previous three-dimensional representation value to estimate a distance difference and of a distance difference greater than a distance threshold. The combination would have been obvious because Powers already limits updating and merging to the voxel blocks inside the current view and re-meshes only the voxel blocks that underwent a truncated signed distance function update, so Powers is expressly trying to avoid repeated work on scene content that has not changed, yet Powers never says how a voxel block is judged to have changed and supplies no test by which a changed block can be told from an unchanged one. Schoenberg supplies exactly that test, comparing the updated signed distance field values against the previous signed distance field values for each voxel as new depth information arrives, summing the value differences over each subset of voxels, and gating regeneration of the mesh for that subset on whether the summed difference is greater than a threshold, preserving the previous mesh reconstruction for the subset when it is not. Schoenberg gives its own purpose as computational and power savings obtained by not regenerating mesh that would be substantially similar to the mesh already held, which is the same saving Powers pursues when it confines updating, merging and re-meshing to the voxel blocks in the current view, and both references hold signed distance values on a voxel grid and extract their mesh by marching cubes, so Schoenberg's test reads the very values Powers already stores in each voxel block and gates the very marching cubes step Powers already performs. A person of ordinary skill working on Powers's per block update would therefore have looked to Schoenberg for the missing measure of change, and applying Schoenberg's comparison and threshold to the truncated signed distance function values Powers maintains sends to mesh generation only those voxel blocks whose values have moved from their previous values by more than the threshold while the mesh already built for the remaining blocks is kept, which further reduces the computation and bandwidth Powers seeks to conserve and leaves untouched the manner in which Powers accumulates depth data and pose data into voxel blocks.
Molyneaux discloses generating a simplified 3D mesh based on the generated 3D mesh (para 208, “A mesh, for example, may be simplified by reducing the number of such polygons in the mesh. As a specific example, the first simplification operation may employ a triangle reduction algorithm, which may reduce the number of triangles used to represent the XR environment.”; also, para 228, “At act 3012, a pre-simplification operation may be performed on a selected first mesh block to generate a second mesh block. The pre-simplification operation may reduce the complexity of the block. For a mesh block, the pre-simplification may reduce the number of polygons in the mesh block.”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further modified Powers in view of Schoenberg, in which the voxel blocks whose truncated signed distance function values differ from their previous values by more than a distance threshold are identified and a three-dimensional mesh is generated from those identified voxel blocks, with the features of Molyneaux's invention of generating a simplified three-dimensional mesh based on the generated three-dimensional mesh. The combination would have been obvious because the mesh that Powers builds by merging the sub meshes of many voxel blocks into a single global mesh grows steadily as the physical environment is scanned, and Powers performs that reconstruction on mobile devices whose memory and rendering capacity are bounded, so the base combination produces an ever larger mesh and has no operation of any kind that reduces its size. Molyneaux works on mesh representations of the same kind of scanned environment and answers exactly that need, teaching that a mesh is simplified by reducing the number of polygons in it, that a simplification operation employing a triangle reduction algorithm reduces the number of triangles used to represent the environment, and that a pre-simplification operation performed on a selected mesh block reduces the complexity of that block, so a person of ordinary skill facing the unbounded growth of the global mesh of Powers would have looked to Molyneaux for the polygon reducing operation the base combination lacks. Passing the mesh generated from the changed voxel blocks to Molyneaux's simplification yields a mesh carrying the same reconstructed scene surface with fewer polygons and therefore a lower memory and rendering cost on the mobile devices Powers targets, and because the simplification acts on the finished mesh it leaves unchanged the manner in which Powers accumulates depth data into voxel blocks and extracts sub meshes from them.
Regarding claim 25, Powers as modified by Schoenberg and Molyneaux discloses the method of claim 24, wherein Powers further disclose the respective 3D representation values are truncated signed distance function (TSDF) values or point cloud values (para 40, “Further, since each edge index encodes two end points, the system may determine the TSDF values of the two voxel end points and then update the associated vertex position without calculating the faces, as is discussed in more detail below.”; also, para 26, “In one example, the viewpoints may be accumulated together as a volume of voxels using a Truncated Signed Distance Function (TSDF) that accumulates information about the scene geometry over time (e.g., over viewpoints).”; also, para 37, “The unbounded TSDF volume may be partitioned into units called voxel blocks, each formed by a plurality of voxels.”).
Regarding claim 27, Powers as modified by Schoenberg and Molyneaux discloses the method of claim 24, wherein Powers further discloses the 3D mesh is generated based on a marching cube algorithm (para 39, “For instance, each voxel block may be configured to store a sub-mesh which is determined from the voxel TSDF using a marching cubes technique.”; also, para 40, “In the current example, the system may perform marching cubes using the voxel blocks by creating a vertex on an edge between two adjacent voxels (with different signs), either in x, y or z direction.”).
Regarding claim 28, Powers as modified by Schoenberg and Molyneaux discloses the method of claim 24, wherein Molyneaux further discloses the simplified 3D mesh is generated based on fusing one or more triangles together within the generated 3D mesh (para 192, “For example, plane detection 1404 may compare primitive normals of each mesh triangle in a sub-brick; merge those mesh triangles, with primitive normal differences smaller than a predetermined threshold value, into one mesh triangle; and identify a mesh triangle with an area larger than a predetermined area value as a plane.”; also, para 190, “Mesh bricks 1308 may be extracted from the SDFs 1306 by, for example, applying a marching cube algorithm over corresponding bricks”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further modified Powers in view of Schoenberg, in which the voxel blocks whose truncated signed distance function values have changed by more than a distance threshold are identified and a three-dimensional mesh is generated from those voxel blocks, with the features of Molyneaux's invention of generating the simplified three-dimensional mesh based on fusing one or more triangles together within the generated three-dimensional mesh. The combination would have been obvious because the base combination merges the sub meshes stored in its voxel blocks into a single global mesh whose triangle count grows with the size of the scanned environment and provides no mechanism for combining neighbouring triangles once they are produced. Molyneaux supplies that mechanism for a mesh of exactly the same kind, one extracted from a signed distance field by a marching cube algorithm, teaching that the primitive normals of each mesh triangle are compared and that those triangles whose normals differ by less than a predetermined threshold are merged into one mesh triangle, so triangles lying on a common surface are joined into a single larger triangle rather than being individually retained. A person of ordinary skill confronting the growing triangle count of the global mesh of the base combination on the mobile device it runs on would have looked to Molyneaux, which treats the same problem of representing a scanned environment with fewer primitives, and applying the merge to the mesh the base combination already produces yields a mesh carrying the same scene surface with fewer triangles and a correspondingly lower memory and rendering cost.
Regarding claim 29, Powers as modified by Schoenberg and Molyneaux discloses the method of claim 28, wherein Molyneaux further discloses the simplified 3D mesh is generated further based on minimizing a number of triangles used for the simplified 3D mesh (para 210, “A second simplification operation that follows the region-based operation may further simplify the representation of the environment, such as by further reducing the number of polygons in the representation. The second simplification operation may focus on reducing the number of polygons within each region detected by the region-based operation.”; also, para 229, “For example, processing in act 3014 may require a minimum number of triangles and a target value provided by an application may be replaced by that minimum value if the target value is below the minimum number of triangles.”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further modified Powers in view of Schoenberg, in which the voxel blocks whose truncated signed distance function values have changed by more than a distance threshold are identified and a three-dimensional mesh is generated from those voxel blocks and simplified, with the features of Molyneaux's invention of generating the simplified three-dimensional mesh further based on minimizing a number of triangles used for the simplified three-dimensional mesh. The combination would have been obvious because the base combination already merges the mesh triangles lying on a common surface into one mesh triangle, which is the region-based operation of Molyneaux, and having done so it stops, leaving whatever triangle count that merge happens to produce. Molyneaux teaches the stage that comes next, a second simplification operation that follows the region-based operation and further simplifies the representation by further reducing the number of polygons within each region the region-based operation detected, and teaches that the reduction is driven toward a target value bounded below by a minimum number of triangles so that it is carried as far as the downstream processing permits. A person of ordinary skill who had merged the coplanar triangles of the base combination would have looked to Molyneaux for that following stage, because Molyneaux places the two operations in that order in one pipeline and describes the second as operating on the regions the first produced, and applying it drives the triangle count of the simplified mesh down to the smallest number that still represents the scanned surface, which conserves the memory and rendering budget of the mobile device the base combination runs on.
Claim(s) 3 and 26 is/are rejected under 35 U.S.C. 103 as being unpatentable over Powers et al. (U.S. Pub. No. 20190318547) as modified by Schoenberg (U.S. Pub. No. 20160364907) and Molyneaux et al. (U.S. Pub. No. 20190197774), further in view of Sokolova et al. (U.S. Pub. No. 20240346765).
Regarding claim 3, Powers as modified by Schoenberg and Molyneaux discloses the apparatus of claim 2, TSDF values are generated based on deep- learning that operates on one or more red, green, blue (RGB) images of the scene and the pose data.
However, in a similar field of endeavor, Sokolova discloses wherein the TSDF values are generated based on deep- learning that operates on one or more red, green, blue (RGB) images of the scene and the pose data (para 43, “A base neural network is any known neural network implementing obtaining a TSDF volume for voxels of a scene from a sequence of RGB frames with camera poses. The base neural network includes a backbone and a TSDF head.”; also, para 69, “The above operations happen repeatedly in the process of training the base neural network. However, only the first operation is carried out when operating of the already trained base neural network. Inputted training data are only used for training, and while operating of the trained base neural network inputted data are RGB frames and camera pose in space.”; also, para 49, “NSR is introduced, a modification of 3D scene reconstruction methods, which includes a novel trainable module and an associated training procedure with normal-segmentation losses of the base neural network on a data set, for which there is a video with camera positions and angles, ground truth reconstructions and segmentation markup of floors and walls.”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further modified Powers in view of Schoenberg and Molyneaux, in which the apparatus accumulates depth and pose data into voxel blocks holding truncated signed distance function values, detects the blocks whose values changed by more than a threshold, meshes those blocks, and simplifies the resulting mesh, with the features of Sokolova's invention of generating the truncated signed distance function values based on deep learning that operates on one or more red, green, blue images of the scene and the pose data. The combination would have been obvious because the base combination derives its truncated signed distance function values from depth image data together with the pose of the mobile device at the time the image data was captured, which ties the reconstruction to a device carrying a depth sensor, and Sokolova teaches that a trained neural network having a truncated signed distance function head obtains a truncated signed distance function volume for the voxels of a scene directly from a sequence of red, green, blue frames with camera poses, so a person of ordinary skill seeking to run the same reconstruction on the many mobile devices that carry a camera but no depth sensor would have looked to Sokolova, which answers that recognized need in the same field of three-dimensional scene reconstruction. Sokolova's trained network emits the same per-voxel truncated signed distance function quantity, organized as a volume over the voxels of the scene, that the base combination already stores in its voxel blocks, so it is a second known source of those values feeding an interface the base combination already has, and the result is a reconstruction that proceeds from color imagery and camera pose alone on the large population of devices that carry a camera but no depth sensor, while the comparison of each value against its previous value, the identification of the changed blocks, the meshing of those blocks, and the simplification of the resulting mesh all continue to operate on values of the kind they already consume.
Regarding claim 26, Powers as modified by Schoenberg and Molyneaux discloses the method of claim 25, TSDF values are generated based on deep- learning that operates on one or more red, green, blue (RGB) images of the scene and the pose data.
However, in a similar field of endeavor, Sokolova discloses wherein the TSDF values are generated based on deep- learning that operates on one or more red, green, blue (RGB) images of the scene and the pose data (para 43, “A base neural network is any known neural network implementing obtaining a TSDF volume for voxels of a scene from a sequence of RGB frames with camera poses. The base neural network includes a backbone and a TSDF head.”; also, para 69, “The above operations happen repeatedly in the process of training the base neural network. However, only the first operation is carried out when operating of the already trained base neural network. Inputted training data are only used for training, and while operating of the trained base neural network inputted data are RGB frames and camera pose in space.”; also, para 49, “NSR is introduced, a modification of 3D scene reconstruction methods, which includes a novel trainable module and an associated training procedure with normal-segmentation losses of the base neural network on a data set, for which there is a video with camera positions and angles, ground truth reconstructions and segmentation markup of floors and walls.”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further modified Powers in view of Schoenberg and Molyneaux, in which truncated signed distance function values held per voxel block are compared against their previous values to identify the changed voxel blocks, a three-dimensional mesh is generated from those voxel blocks, and that mesh is simplified, with the features of Sokolova's invention of generating the truncated signed distance function values based on deep learning that operates on one or more red, green, blue images of the scene and the pose data. The combination would have been obvious because Powers ties its reconstruction to a device that carries a depth sensor, deriving every truncated signed distance function value from the depth frames that sensor produces, so the base combination cannot be run at all on the many mobile devices that carry a camera but no depth sensor, and one of ordinary skill would have sought to run the same reconstruction on those devices. Sokolova answers that recognized need directly, teaching a trained network with a backbone and a truncated signed distance function head that obtains the truncated signed distance function volume for the voxels of a scene from a sequence of red, green, blue frames with camera poses, and teaching that once the network is trained the data it takes in operation are red, green, blue frames and camera pose in space, which are exactly the inputs such a device produces and which Powers already captures as color image data and a pose of the mobile device. A person of ordinary skill would further have looked to Sokolova because Sokolova trains its module with normal and segmentation losses against ground truth reconstructions in order to raise the quality of the reconstructed scene geometry, which is the same reconstruction quality Powers pursues. Deriving the truncated signed distance function values from Sokolova's trained network gives a volume of the same form on the same voxel grid that the remainder of the method partitions into voxel blocks, compares, meshes and simplifies exactly as before, now obtained from red, green, blue frames and camera poses rather than from depth frames.
Claim(s) 7 is/are rejected under 35 U.S.C. 103 as being unpatentable over Powers et al. (U.S. Pub. No. 20190318547) as modified by Schoenberg (U.S. Pub. No. 20160364907) and Molyneaux et al. (U.S. Pub. No. 20190197774), further in view of Min et al. (U.S. Pub. No. 20170301133).
Regarding claim 7, Powers as modified by Schoenberg and Molyneaux discloses the apparatus of claim 6, minimize the number of triangles, the at least one processor is configured to remove redundant triangles.
However, in a similar field of endeavor Min discloses wherein, to minimize the number of triangles, the at least one processor is configured to remove redundant triangles (para 31, “To achieve high quality merging, mesh-clipping may be applied to automatically clip off geometrically redundant triangles in the overlapping regions.”; also, para 54, “According to some embodiments, the redundant vertices may be clipped off (i.e., removed). It may be advantageous to clip off the redundant vertices for several reasons. For example, the redundant mesh triangles may have different geometries and textures with respect to one another, and thus may potentially be shown as apparent artifacts if not clipped.”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further modified Powers in view of Schoenberg and Molyneaux, in which the apparatus detects the changed voxel blocks, generates a three-dimensional mesh from them, and reduces the triangle count of that mesh toward a target, with the features of Min's invention of removing redundant triangles in order to minimize the number of triangles. The combination would have been obvious because the base combination merges multiple sub-meshes taken from multiple voxel blocks into one global mesh, a merging operation that produces overlapping regions in which the same surface is represented more than once, and the base combination provides no step for discarding that duplicated geometry, while Min teaches clipping off geometrically redundant triangles in exactly those overlapping regions to achieve high quality merging and warns that redundant mesh triangles left in place appear as artifacts, so a person of ordinary skill merging sub-meshes and then reducing the triangle count would have looked to Min, which answers the very defect that merging creates. Min's clipping is described for merged triangle meshes of overlapping captures of a scene, which is exactly the mesh the base combination's block-wise merging produces, so the clipping runs on that merged mesh ahead of the triangle reduction and discards the duplicated surface first, with the consequence that the triangle count falls without any loss of surface actually represented and the artifacts Min attributes to redundant triangles of differing geometry and texture do not survive into the displayed reconstruction.
Claim(s) 8 and 30 is/are rejected under 35 U.S.C. 103 as being unpatentable over Powers et al. (U.S. Pub. No. 20190318547) as modified by Schoenberg (U.S. Pub. No. 20160364907) and Molyneaux et al. (U.S. Pub. No. 20190197774), further in view of Deleplace et al. (U.S. Pub. No. 20170228894 ).
Regarding claim 8, Powers as modified by Schoenberg and Molyneaux discloses the apparatus of claim 5, at least one processor is configured to fuse triangles within the generated 3D mesh until a hardware limit is reached based on a number of triangles within the simplified 3D mesh.
However, in a similar field of endeavor, Deleplace discloses wherein the at least one processor is configured to fuse triangles within the generated 3D mesh until a hardware limit is reached based on a number of triangles within the simplified 3D mesh (para 58, “Next step 506 allows applying a calibrated decimation if the total number of triangles of the initial 3D model exceeds a predefined threshold. The predefined threshold is defined as a target parameter depending on the target device for the rendering of the 3D model.”; also, para 59, “In an application, the maximum numbers of triangles is of the order of 2 millions of triangles. The process of the invention allows by the successive steps to decimate a 3D model down to 2 millions of triangles to have it displayed in real time on tablets and mobile devices. In this application, the threshold for applying the calibrated decimation step is set to 2 millions of triangles.”; also, para 52, “For each pair, computing the best point for collapsing and the associated error; then inserting the pairs into an error ranking priority list, and collapsing the top pair. The process is repeated to obtain a fixed number of faces or a maximum defined error.”; also, para 54, “Simplification operations comprise collapsing one or more edges by combining one or more vertices, using quadric errors, using simplification envelopes or parallel mesh simplification, distributed simplification, parallel hierarchical level of detail or parallel view-dependent mesh refinement.”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further modified Powers in view of Schoenberg and Molyneaux, in which the apparatus detects the changed voxel blocks, generates a three-dimensional mesh from them, and fuses triangles within that mesh to produce a simplified mesh, with the features of Deleplace's invention of fusing triangles within the generated three-dimensional mesh until a hardware limit is reached based on a number of triangles within the simplified three-dimensional mesh. The combination would have been obvious because the base combination fuses triangles but leaves the stopping point of that fusion undefined, and Deleplace supplies exactly that stopping point by teaching that its simplification collapses edges by combining vertices, that the collapsing is repeated until a fixed number of faces is obtained, and that the decimation continues until the model is brought down to a maximum triangle count fixed by the target device so the model can be displayed in real time on tablets and mobile devices, and the base combination builds its global mesh on precisely such a mobile device, so a person of ordinary skill would have looked to Deleplace for the device-dependent bound the base combination lacks. Deleplace's bound is a termination condition on an edge collapse process of the same kind the base combination already carries out, so it governs the fusion that is already there rather than replacing it, and it yields a simplified mesh whose triangle count is held within the capacity of the hardware that must render it, so the reconstruction is displayed at interactive rates on the tablets and mobile devices that both Deleplace and Powers address instead of growing with the extent of the scanned environment until the device can no longer render it.
Regarding claim 30, Powers as modified by Schoenberg and Molyneaux discloses the method of claim 28, fusing triangles within the generated 3D mesh until a hardware limit is reached based on a number of triangles within the simplified 3D mesh.
However, in a similar field of endeavor, Deleplace discloses further comprising fusing triangles within the generated 3D mesh until a hardware limit is reached based on a number of triangles within the simplified 3D mesh (para 58, “Next step 506 allows applying a calibrated decimation if the total number of triangles of the initial 3D model exceeds a predefined threshold. The predefined threshold is defined as a target parameter depending on the target device for the rendering of the 3D model.”; also, para 59, “In an application, the maximum numbers of triangles is of the order of 2 millions of triangles. The process of the invention allows by the successive steps to decimate a 3D model down to 2 millions of triangles to have it displayed in real time on tablets and mobile devices. In this application, the threshold for applying the calibrated decimation step is set to 2 millions of triangles.”; also, para 52, “For each pair, computing the best point for collapsing and the associated error; then inserting the pairs into an error ranking priority list, and collapsing the top pair. The process is repeated to obtain a fixed number of faces or a maximum defined error.”; also, para 54, “Simplification operations comprise collapsing one or more edges by combining one or more vertices, using quadric errors, using simplification envelopes or parallel mesh simplification, distributed simplification, parallel hierarchical level of detail or parallel view-dependent mesh refinement.”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further modified Powers in view of Schoenberg and Molyneaux, in which the voxel blocks whose truncated signed distance function values have changed by more than a distance threshold are identified, a three-dimensional mesh is generated from those voxel blocks, and triangles within that mesh are fused to produce a simplified three-dimensional mesh, with the features of Deleplace's invention of fusing triangles within the generated three-dimensional mesh until a hardware limit is reached based on a number of triangles within the simplified three-dimensional mesh. The combination would have been obvious because the base method fuses triangles to reduce the reconstructed mesh but ties the amount of that reduction to nothing outside the mesh itself, so it has no stopping condition set by the capability of the device that must render the result. Deleplace supplies exactly such a stopping condition, teaching that a calibrated decimation is applied when the total number of triangles of the model exceeds a predefined threshold, that the threshold is defined as a target parameter depending on the target device for the rendering of the model, and that the edge collapse simplification which combines vertices is repeated to obtain a fixed number of faces, and giving the concrete case of decimating a model down to two million triangles so that it can be displayed in real time on tablets and mobile devices. Those are the very devices on which Powers captures and reconstructs the physical environment in real time, so a person of ordinary skill working on the base method would have had a clear design incentive to look to Deleplace for the device dependent bound the base method lacks, and repeating the fusing of triangles until the triangle count reaches the value set for the target device gives a simplified mesh that fits within the capability of the rendering device while continuing to represent the scanned scene surface, with no change to the way Powers integrates depth data into voxel blocks or extracts the mesh from them.
Allowable Subject Matter
Claim 10-23 allowed.
Claim 9 objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
The following is a statement of reasons for the indication of allowable subject matter:
Claim 9 requires that triangles be fused within the generated three-dimensional mesh until a threshold compression ratio is reached, so the fusing terminates on the proportion by which the mesh has been reduced. The closest art halts its simplification at an absolute count of vertices, polygons, or edges fixed in advance, and mentions a compression ratio only when comparing the visual quality of meshes that have been reduced by the same amount, which is a statement about the quality of a result rather than a condition that stops the reduction. A budget expressed as a count is not a threshold expressed as a ratio, so the art does not reach the limitation.
Claim 10 requires that the simplified three-dimensional mesh be generated based on the one or more portions of the generated three-dimensional mesh identified as having vertices whose distance difference from the corresponding previous vertices exceeds a distance threshold, so the portions that drive the simplification are the portions the comparison found to have changed. The closest art performs its simplification on a subset of mesh blocks chosen from the objects those blocks describe or from where those blocks lie, which is a selection made from the content and position of the geometry rather than from any measurement of how far that geometry has moved since a previous mesh, and no art was located that measures per vertex displacement against a previous mesh and then feeds the portions so identified into the simplification. A selection made on what a block contains does not become a selection made on what has changed, so the art does not reach the limitation.
Claims 11 to 16 depend from claim 10 and are allowable for the same reason.
Claim 17 requires that a final three-dimensional mesh be generated based on the one or more portions of the simplified three-dimensional mesh identified as having vertices whose distance difference from the corresponding previous vertices exceeds a distance threshold, so the mesh that issues from the pipeline is built from the changed portions of an already simplified mesh. The closest art simplifies a subset of mesh blocks picked according to the objects described in those blocks or their locations, and separately compares the vertices of a scanned surface against an earlier scan of the same surface to find where it has moved, but nothing was located that compares the vertices of a simplified mesh against corresponding previous vertices or that builds an output mesh from the portions of a simplified mesh so identified. The art therefore reaches neither the comparison performed on the simplified mesh nor the construction of the final mesh from its changed portions.
Claims 18 to 23 depend from claim 17 and are allowable for the same reason.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Jai Li whose telephone number is (571)272-1170. The examiner can normally be reached Mon-Thu between 06:00-16:00 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, Xiao Wu can be reached at (571)272-7761. 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.
/JAI W LI/Junior Examiner, Art Unit 2613
/XIAO M WU/Supervisory Patent Examiner, Art Unit 2613
Prosecution Insights