Normal orientation with MST : implement Xie's method

[jean-loup]

Hi Daniel,

I've been using CloudCompare for orienting normals for large point-clouds, mainly using the Minimum Spanning Tree method. So far it has been a great help but I would like to suggest adding a slighty new functionality :

Correct me if I'm wrong but the algorithm implemented in CloudCompare is similar to the one described in Hoppe's et al. article Surface reconstruction from unorganized points (1992) which considers that the normal orientation should be propagated along nearly parallel planes. It is a good approximation for planar or low curvature surfaces but it results in incorrectly flipped normals along sharp edges or nearby sheets.

Xie et al. Piecewise C1 continuous surface reconstruction of noisy point clouds via local implicit quadric regression (2003) have proposed an improvement to Hoppe's method by considering that the underlying surface is of constant curvature. The approach is very similar to Hoppe's one but uses a slightly different criteria to determine if a normal is consistently oriented or not (see also König and Gumhold's article Consistent Propagation of Normal Orientations in Point Clouds (2009)).

I've compared the two algorithms myself (python script) with various data sets and Xie's method gives much better results along sharp edges and nearby sheets than Hoppe's, the computation time is just a few percent (~5-10%) longer. It may be nice to have the two methods in CloudCompare !

[daniel]

Indeed, this is Hope's algorithm that is implemented in CC currently. Thanks for the improvement suggestion.

Could you maybe share your Python code with me? (admin [at] cloudcompare.org)