Point cloud simplification

1. A computer implemented method for simplification of a point cloud that represents one or more three-dimensional objects or surfaces, the point cloud including a set of points, the method comprising:

receiving the point cloud and storing the point cloud in a memory;

implementing, with a processor, recursive spatial partitioning of the set of points into a hierarchy of clusters;

identifying, with a processor, representative points within each cluster in the hierarchy; and,

for each representative point, defining a point-pair that includes the representative point and a representative point of an immediate parent cluster, and calculating a contraction error metric for each point-pair; and

generating, with a processor, a simplified point cloud that represents the one or more three-dimensional objects or surfaces using a reduced number of points by iteratively contracting the point-pair with the lowest contraction error metric, updating remaining point-pairs as a result of the contraction, and revising the contraction error metric of the updated point-pairs accordingly.

2. The method of claim 1 , wherein the recursive spatial partitioning of the set of points into a hierarchy of clusters comprises implementing divisive hierarchical clustering of the set of points.

3. The method of claim 1 , wherein the recursive spatial partitioning of the set of points into a hierarchy of clusters comprises: partitioning an initial root cluster comprising the set of points into a number of clusters; recursively partitioning each cluster into further clusters until either each cluster contains a single point or a predefined depth is reached.

4. The method of claim 1 , wherein the step of identifying representative points within each cluster in the hierarchy comprises:

for a cluster in the hierarchy that has at least one child cluster, identifying the point that is closest to the mean of the points within the cluster as a representative point; and for a cluster in the hierarchy that has no child cluster, identifying each point within the cluster as a representative point.

5. The method of claim 1 , and further comprising:

generating a logical tree by defining the representative points as nodes of the logical tree, and, for each representative point, defining an edge of the logical tree as a point-pair that consists of the representative point and a representative point of an immediate parent cluster.

6. The method of claim 5 , wherein the step of updating remaining point-pairs as a result of the contraction comprises:

updating the logical tree as a result of the contraction of the point-pair.

7. The method of claim 1 , and further comprising:

defining a contraction queue in which the point-pair with the lowest contraction error metric is first in the contraction queue; and after each contraction, updating the contraction queue to reflect updates in the calculated contraction error metrics of the updated point-pairs.

8. The method of claim 1 , wherein the step of updating remaining point-pairs as a result of the contraction comprises:

identifying other point-pairs that include either of the points that were included in the contracted point-pair, and updating the identified point-pairs to include a new point generated as a result of the contraction.

9. The method of claim 8 , wherein the step of revising the contraction error metric of the updated point-pairs accordingly comprises:

for each of the point-pairs that are updated to include a new point generated as a result of the contraction, recalculating the contraction error metric using the new point.

10. The method of claim 1 , wherein the iterative contraction of the point-pair with the lowest contraction error metric continues until a predefined stop criteria is met.

11. The method of claim 1 , wherein the contraction of the point-pair with the lowest contraction error metric comprises replacing the point-pair with a new point.

12. The method of claim 11 , wherein the step of replacing the point-pair with a new point comprises either of:

selecting a position of one of the points in the point-pair that results in the lowest contraction error metric for the corresponding contraction and generating a new point at the selected position; and determining a position that minimises the contraction error metric for the corresponding contraction and generating a new point at the determined position.

13. The method of claim 1 , wherein the contraction error metric is a sum of the squared distances between a new point generated as a result of the contraction and each point in an affiliated set of points arising from the contraction of the point-pair.

14. The method of claim 1 , wherein the contraction error metric is a quadric error metric.

15. A non-transitory computer readable medium storing computer interpretable instructions which when interpreted by a programmable computer cause the computer to perform a method in accordance claim 1 .

16. A computer system for implementing simplification of a point cloud that represents one or more three-dimensional objects or surfaces, the point cloud comprising a set of points, the system comprising:

a memory configured to store the point cloud; and

a processor configured to:

implement recursive spatial partitioning of the set of points into a hierarchy of clusters;

identify representative points within each cluster in the hierarchy and, for each representative point, define a point-pair that includes the representative point and a representative point of an immediate parent cluster; calculate a contraction error metric for each point-pair; and

generate a simplified point cloud that represents the one or more three-dimensional objects or surfaces using a reduced number of points by iteratively contract the point-pair with the lowest contraction error metric, updating remaining point-pairs as a result of the contraction, and revising the contraction error metric of the updated point-pairs accordingly.