Methods and systems for constructing map data using poisson surface reconstruction

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.