Poisson Reconstruction crashes with high density datasets

[sgiraudot]

Issue Details

Our version of Poisson is not robust at all and is very prone to crashes and memory explosions. This happens a lot for densely sampled point clouds. The reason is that the support Delaunay 3D uses all points of the input + a refinement step, which can lead to an overly dense triangulation for no gain in quality.

I have 2 leads on how to solve this:

• we discussed it with @palliez and figured we could use an Octree, not for the discretization of the function as is done in the original paper by Kazhdan, but just to use the vertices to build the triangulation. That would be a way to have the best of both worlds. This was developed with the idea of integrating Spectral Reconstruction to the package and there is a prototype in an experimental branch. Also, an Octree should be integrated soon in CGAL, which could be used for this.
• we could do a Delaunay refinement that would just be guided by an error tolerance on the normals instead of using input points directly: before adding a point, we should locate it, and estimate the normal at his position through barycentric coordinates in the cell. If the error between the estimated normal and the normal of the point is low, then it's useless to add it, as it does not bring useful information (= the surface does not change here, the point is just there because of a high sampling). This would be similar to what we did in Noise Adaptive Shape Reconstruction (section 3.1).

Dataset

An example dataset that makes CGAL Poisson run for 20 minutes before memory explosion. Note that there are a few misoriented normals, but the Meshlab version of Poisson manages to create a correct output in a few minutes on this dataset, so this should not be a problem.

[MaelRL]

Would be interesting to see if the octree-only Screened Poisson suffers from the same issues, since it already has the benefit of giving better results (from a quality PoV) than Delaunay-based Poisson.