Mesh estimation of terrain
A method for generating a three dimensional grid of terrain includes receiving data representing a three-dimensional point cloud and generating a plurality of slices of the data. The method evaluates the slices using a swarm intelligence algorithm. The method is able to identify both terrain and objects. The terrain can also be identified as traversable terrain.
1. A method for generating a three dimensional grid of terrain, comprising the steps:
receiving data representing a three-dimensional point cloud;
generating a plurality of slices of the data;
evaluating the slices using a swarm intelligence algorithm;
identifying terrain as a function of the evaluation; and
generating a three-dimensional grid of the identified terrain.
2. The method of claim 1 further comprising the step of displaying the identified terrain.
3. The method of claim 1 further comprising the step of storing the identified terrain in a memory device.
4. The method of claim 1 wherein the identified terrain is identified as traversable terrain.
5. The method of claim 4 further including the steps of:
identifying at least a portion of the terrain as non-traversable terrain; and
defining the non-traversable terrain as at least one object.
6. The method of claim 1 wherein the plurality of slices are longitudinal and lateral slices.
7. The method of claim 1 wherein the plurality of slices are radial and concentric slices.
8. The method of claim 1 wherein the swarm intelligence algorithm compensates for missing terrain data.
9. The method of claim 1 further comprising the step of:
accumulating points normal to the two-dimensional reference plane into pixels of brightness proportional to the number of points accumulated, the pixel brightness indicating terrain of substantially equal elevation.
10. A method for generating a three dimensional map of terrain, comprising the steps:
receiving data representing a three dimensional point cloud;
generating a series of three-dimensional slices of the data;
accumulating points normal to two-dimensional reference planes into a series of two-dimensional planes;
identifying a lowest cost path across each of the series of the two-dimensional planes using a swarm intelligence algorithm; and
merging the lowest cost paths to produce a three-dimensional grid of terrain.
11. The method of claim 10 further comprising the step of displaying the identified terrain.
12. The method of claim 10 further comprising the step of storing the identified terrain in a memory device.
13. The method of claim 10 wherein the identified terrain is identified as traversable terrain.
14. The method of claim 13 further including the steps of:
identifying at least a portion of the terrain as non-traversable terrain; and
defining the non-traversable terrain as at least one object.
15. The method of claim 10 wherein the plurality of slices are longitudinal and lateral slices.
16. The method of claim 9 wherein the plurality of slices are radial and concentric slices.
17. The method of claim 9 wherein the swarm intelligence algorithm defines missing terrain data.
18. The method of claim 10 further comprising the step of:
accumulating points normal to the two-dimensional reference plane into pixels of brightness proportional to the number of points accumulated, the pixel brightness indicating terrain of substantially equal elevation.
19. A method for analyzing three-dimensional terrain using a two-dimensional algorithm, comprising the steps:
receiving data representing a three-dimensional point cloud;
generating a plurality of three-dimensional slices, each associated with a two-dimensional reference plane; and
accumulating points normal to the two-dimensional reference plane into pixels of brightness proportional to the number of points accumulated, the pixel brightness indicating terrain of substantially equal elevation.
20. A computer-based system for generating a three-dimensional grid of terrain, comprising:
a receiving module for receiving data representing a three-dimensional point cloud;
a slice generating module for generating a plurality of slices of the data;
a swarm intelligence module for evaluating the slices using a swarm intelligence algorithm;
a terrain identifying module for identifying terrain as a function of the evaluation; and
a three-dimensional grid generating module for generating a three-dimensional grid of the identified terrain.