Methods and systems for constructing map data using poisson surface reconstruction

Abstract

A method and a system for generating a mesh representation of a surface. The method includes receiving a three-dimensional (3D) point cloud representing the surface, generating a reconstruction dataset having a higher resolution than the 3D point cloud in one or more regions corresponding to the surface from the 3D point cloud, and generate a polygon mesh representation of the surface by using a fine-to-coarse hash map for building polygons at a highest resolution first followed by progressively coarser resolution polygons, using the reconstruction dataset.

The invention claimed is: 
     
       1. A method for generating a mesh representation of a surface comprising:
 receiving a three-dimensional (3D) point cloud representing the surface; 
 generating, from the 3D point cloud, a reconstruction dataset having a higher resolution than the 3D point cloud in one or more regions corresponding to the surface; and 
 generating, using the reconstruction dataset, a polygon mesh representation of the surface by using a fine-to-coarse hash map for building polygons at a highest resolution first followed by progressively coarser resolution polygons. 
 
     
     
       2. The method of  claim 1 , further comprising using the polygon mesh representation for navigating an autonomous vehicle over the surface. 
     
     
       3. The method of  claim 1 , wherein the hash map comprises:
 a plurality of keys, each key corresponding to a voxel edge; and 
 a plurality of values, each value corresponding to a vertex location. 
 
     
     
       4. The method of  claim 3 , wherein using the fine-to-coarse hash map for building polygons at the highest resolution first followed by progressively coarser resolution polygons comprises:
 before insertion of a new vertex to an edge of the polygon mesh representation, using the hash map to determine whether a first vertex exists on the edge; 
 in response to determining that the first vertex exists on the edge, deriving a location of the first vertex from the hash map; and 
 using the derived location for building a polygon. 
 
     
     
       5. The method of  claim 1 , wherein generating the polygon mesh representation comprises detecting and filling holes in the polygon mesh representation by:
 generating a list of edges that comprises a plurality of edges which have been used once in the polygon mesh representation; and 
 building polygons starting from a first vertex in an implicit surface corresponding to the reconstruction dataset and using a list of edges until reaching the first vertex such that each of the plurality of edges is used at least twice in the polygon mesh representation. 
 
     
     
       6. The method of  claim 1 , wherein the polygon mesh representation does not include any topological holes. 
     
     
       7. The method of  claim 1 , wherein the polygon mesh representation is a triangle mesh representation. 
     
     
       8. The method of  claim 1 , wherein generating the reconstruction dataset comprises identifying and discarding one or more outliers in the 3D point cloud to generate a filtered point cloud using a Gaussian process by:
 identifying a Gaussian surface corresponding to the 3D point cloud; 
 determining a mean Gaussian surface from the Gaussian surface; and 
 identifying the one or more outliers as points in the 3D point cloud that have a standard deviation from the mean Gaussian surface that is greater than a threshold standard deviation. 
 
     
     
       9. The method of  claim 1 , wherein generating the reconstruction dataset comprises identifying and discarding one or more outliers in the 3D point cloud to generate a filtered point cloud using a Gaussian process by:
 identifying a Gaussian surface corresponding to the 3D point cloud; 
 determining a mean Gaussian surface from the Gaussian surface; and 
 identifying the one or more outliers as points in the 3D point cloud that are located at a physical distance from the mean Gaussian surface that is greater than a threshold physical distance. 
 
     
     
       10. The method of  claim 1 , wherein generating the reconstruction dataset comprises adding one or more additional points to the point cloud by:
 identifying one or more holes in the point cloud; and 
 adding at least one point to each of the one or more holes using a Gaussian surface corresponding to the 3D point cloud. 
 
     
     
       11. The method of  claim 10 , wherein identifying the one or more holes comprises:
 grid-sampling a subset of points in the point cloud to determine whether at least one point of the point cloud exists within a threshold distance from a sampled point; and 
 identifying a hole proximate to the sampled point upon determining that at least one point of the point cloud does not exist within the threshold distance from the sampled point. 
 
     
     
       12. The method of  claim 1 , wherein generating the reconstruction dataset comprises identifying and discarding, from the point cloud, points corresponding to one or more moving objects. 
     
     
       13. A system for generating a mesh representation of a surface comprising:
 a processor; and 
 a non-transitory computer readable medium comprising programming instructions that when executed by the processor will cause the processor to:
 receive a three-dimensional (3D) point cloud representing the surface, 
 generate, from the 3D point cloud, a reconstruction dataset having a higher resolution than the 3D point cloud in one or more regions corresponding to the surface and 
 generate, using the reconstruction dataset, a polygon mesh representation of the surface by using a fine-to-coarse hash map for building polygons at a highest resolution first followed by progressively coarser resolution polygons. 
 
 
     
     
       14. The system of  claim 13 , further comprising programming instructions that when executed by the processor will cause the processor to use the polygon mesh representation for navigating an autonomous vehicle over the surface. 
     
     
       15. The system of  claim 13 , wherein the hash map comprises:
 a plurality of keys, each key corresponding to a voxel edge; and 
 a plurality of values, each value corresponding to a vertex location. 
 
     
     
       16. The system of  claim 15 , wherein the programming instructions that when executed by the processor cause the processor to use the fine-to-coarse hash map for building polygons at the highest resolution first followed by progressively coarser resolution polygons comprise programming instructions to cause the processor to:
 before insertion of a new vertex to an edge of the polygon mesh representation, use the hash map to determine whether a first vertex exists on the edge; 
 in response to determining that the first vertex exists on the edge, derive a location of the first vertex from the hash map; and 
 use the derived location for building a polygon. 
 
     
     
       17. The system of  claim 13 , wherein the programming instructions that when executed by the processor cause the processor to generate the polygon mesh representation comprise programming instructions to cause the processor to detect and fill holes in the polygon mesh representation by:
 generating a list of edges that comprises a plurality of edges which have been used once in the polygon mesh representation; and 
 building polygons starting from a first vertex in an implicit surface corresponding to the reconstruction dataset and using a list of edges until reaching the first vertex such that each of the plurality of edges is used at least twice in the polygon mesh representation. 
 
     
     
       18. The system of  claim 13 , wherein the programming instructions that when executed by the processor cause the processor to generate the reconstruction dataset comprise programming instructions to cause the processor to add one or more additional points to the point cloud by:
 identifying one or more holes in the point cloud; and 
 adding at least one point to each of the one or more holes using a Gaussian surface corresponding to the 3D point cloud. 
 
     
     
       19. The system of  claim 18 , wherein the programming instructions that when executed by the processor cause the processor to identify the one or more holes comprise programming instructions to cause the processor to:
 grid-sample a subset of points in the point cloud to determine whether at least one point of the point cloud exists within a threshold distance from a sampled point; and 
 identify a hole proximate to the sampled point upon determining that at least one point of the point cloud does not exist within the threshold distance from the sampled point. 
 
     
     
       20. A computer program product comprising a non-transitory memory and programming instructions that are configured to cause a processor to:
 receive a three-dimensional (3D) point cloud representing the surface; 
 generate, from the 3D point cloud, a reconstruction dataset having a higher resolution than the 3D point cloud in one or more regions corresponding to the surface; and 
 generate, using the reconstruction dataset, a polygon mesh representation of the surface by using a fine-to-coarse hash map for building polygons at a highest resolution first followed by progressively coarser resolution polygons.