Space carving in 3D data acquisition
Three-dimensional scanning is improved with the use of space carving to exclude certain scan results from processing and display. Using space carving techniques, a spatial matrix is maintained to store data on volumetric regions (or voxels) known to be empty. By excluding or modifying processing of outlier data from within these unoccupied voxels, a three-dimensional reconstruction process can achieve concurrent improvements in accuracy and speed. In addition, a real time display of scan results can be improved by modifying how such outliers are rendered.
1. A method comprising:
storing a spatial matrix in a memory, the spatial matrix including information for a plurality of voxels in a mesh of a scan space;
obtaining three-dimensional data from an object within the scan space using a scanner;
identifying a one of the plurality of voxels in the mesh that is unoccupied;
storing an indication in the spatial matrix for a modified processing of data from the one of the plurality of voxels, thereby identifying a prohibited volume within the scan space; and
processing a portion of the three-dimensional data that is not in the prohibited volume according to an unmodified processing and processing a second portion of the three-dimensional data that is in the prohibited volume according to the modified processing, wherein the modified processing includes detecting a point in the prohibited volume and displaying the point for a decay time with the second portion of the three-dimensional data.
2. The method of claim 1 wherein identifying the one of the plurality of voxels includes identifying a plurality of points on a ray between the scanner and the object that are unoccupied.
3. The method of claim 1 further comprising providing a spatial margin of one or more voxels adjacent to a surface of the object for which processing cannot be prohibited.
4. The method of claim 3 wherein the spatial margin is a multiple of a standard deviation of a z-axis measurement for the scanner.
5. The method of claim 1 wherein the modified processing includes omitting any points in the prohibited volume from a surface mesh of the object created with the three-dimensional data.
6. The method of claim 5 wherein the mesh divides the scan space into a spatial grid substantially identical to a second spatial grid used to create the surface mesh.
7. The method of claim 1 wherein the modified processing includes omitting any points in the prohibited volume from a high-accuracy refinement of the three-dimensional data.
8. The method of claim 1 wherein the mesh of the scan space is subdivided into voxels having a substantially cubic shape.
9. The method of claim 8 wherein the substantially cubic shape measures about 250 microns on each edge.
10. The method of claim 1 wherein the prohibited volume includes more than one of the plurality of voxels.
11. The method of claim 1 wherein the spatial matrix includes a binary flag for each one of the plurality of voxels that indicates whether processing is permitted or forbidden for a corresponding volume of the scan space.
12. A computer program product comprising computer executable code embodied on a non-transitory computer readable medium that, when executing on one or more computing devices, performs the steps of:
storing a spatial matrix in a memory, the spatial matrix storing information for a plurality of voxels in a mesh of a scan space;
obtaining three-dimensional data from an object within the scan space using a scanner;
identifying one of the plurality of voxels in the mesh of the scan space that is unoccupied;
storing an indication in the spatial matrix for a modified processing of data from the one of the plurality of voxels, thereby identifying a prohibited volume within the scan space; and
processing a portion of the three-dimensional data in the prohibited volume according to the modified processing and processing a second portion of the three-dimensional data that is not in the prohibited volume according to an unmodified processing, wherein the modified processing includes detecting a point in the prohibited volume and displaying the point for a decay time with the second portion of the three-dimensional data.
13. The computer program product of claim 12 wherein identifying the one of the plurality of voxels includes identifying a plurality of points on a ray between the scanner and the object that are unoccupied.
14. The computer program product of claim 12 further comprising code for providing a spatial margin of one or more voxels adjacent to a surface of the object for which processing cannot be prohibited.
15. The computer program product of claim 14 wherein the spatial margin is a multiple of a standard deviation of a z-axis measurement for the scanner.
16. The computer program product of claim 12 wherein the modified processing includes omitting any points in the prohibited volume from a surface mesh of the object created with the three-dimensional data.
17. The computer program product of claim 16 wherein the mesh divides the scan space into a spatial grid substantially identical to a second spatial grid used to create the surface mesh.
18. The computer program product of claim 12 wherein the modified processing includes omitting any points in the prohibited volume from a high-accuracy refinement of the three-dimensional data.
19. The computer program product of claim 12 wherein the mesh of the scan space is subdivided into voxels having a substantially cubic shape.
20. The computer program product of claim 19 wherein the substantially cubic shape measures about 250 microns on each edge.
21. The computer program product of claim 12 wherein the prohibited volume includes more than one of the plurality of voxels.
22. The computer program product of claim 12 wherein the spatial matrix includes a binary flag for each one of the plurality of voxels that indicates whether processing is permitted or forbidden for a corresponding volume of the scan space.
23. A system comprising:
a scanner configured to obtain three-dimensional data from an object within a scan space;
a memory configured to store a spatial matrix that includes information for a plurality of voxels in a mesh of the scan space; and
a processor configured to identify a point in the scan space that is unoccupied, to store an indication in the spatial matrix for a modified processing of data from a one of the plurality of voxels that contains the point, thereby identifying a prohibited volume within the scan space, to process a portion of the three-dimensional data that is not in the prohibited volume according to an unmodified processing, and to process a second portion of the three-dimensional data that is in the prohibited volume according to the modified processing, wherein the modified processing includes detecting a point in the prohibited volume and displaying the point for a decay time with the second portion of the three-dimensional data.
24. A computer program product comprising computer executable code embodied on a non-transitory computer readable medium that, when executing on one or more computing devices, performs the steps of:
storing a spatial matrix in a memory, the spatial matrix storing information for a plurality of voxels in a mesh of a scan space;
obtaining three-dimensional data from an object within the scan space using a scanner;
providing a spatial margin of one or more voxels adjacent to a surface of the object for which processing cannot be prohibited, wherein the spatial margin is a multiple of a standard deviation of a z-axis measurement for the scanner;
identifying one of the plurality of voxels in the mesh of the scan space that is unoccupied;
storing an indication in the spatial matrix for a modified processing of data from the one of the plurality of voxels, thereby identifying a prohibited volume within the scan space; and
processing a portion of the three-dimensional data in the prohibited volume according to the modified processing and processing a second portion of the three-dimensional data that is not in the prohibited volume according to an unmodified processing.
25. The computer program product of claim 24 wherein the modified processing includes omitting any points in the prohibited volume from a surface mesh of the object created with the three-dimensional data.
26. The computer program product of claim 25 wherein the mesh divides the scan space into a spatial grid substantially identical to a second spatial grid used to create the surface mesh.