PCL point normals not always calculated correctly in sparse clouds

Your Environment

• Operating System and version: Ubuntu 14.04
• Compiler: GCC v4.8.4
• PCL Version: 1.8.1
• C++ Version: C++11

Context

I'm currently trying to find a point cloud registration method that can accurately match relatively sparse 3D point clouds from one Velodyne HDL-32E. At the moment I am using PCL's implementation of Generalized ICP to match several sequential scans similar to the one shown below.

(This is one scan of a carpark outside an office building with floor-ceiling glass windows, hence little few LiDAR returns from the wall).

I.e. I take one scan like this and try to register it to a scan taken 1-2 cm further forward. Now, matching sequential scans does work in some areas but not in others. Since GICP depends on good normal calculations I've been inspecting some clouds in the PCL visualizer (shown in this tutorial) and I noticed that in some places the normals are not being calculated correctly at all.

Expected Behavior

The normals in most parts of the clouds should be calculated correctly. Or if they aren't, it's obviously because the data is too sparse in that region of the point cloud.

Current Behavior

The normal directions are mostly correct, but in some places where there is plenty of data, they are not calculated correctly. The most obvious place is in this example, where the normals all point more-or-less upwards in the flower bed part of the wall. This is incorrect, the normals should be orthogonal to the wall and pointing out horozontally:

This is the case in this specific area pretty much regardless of whether I use a KNearest or Radius point search, and regardless of the values for K or for the radius.

Code to Reproduce

Try the cloud in question: carpark_cloud.ply

in the PCL visualizer (shown in this tutorial)

Possible Solution

I have two theories on what the cause of the problem is.

1. The data itself is the problem. Because the Velodyne has an error of +/- 2cm any given scan line is not a perfect line but has a thickness, whose maximum width will be about 4 cm (assuming max +/- 2cm error). This means that each scan line actually generates it's own plane of points, and at close ranges there may be enough points packed tightly together in one line that this overrules the plane fitting method PCL uses by default and fits a plane to the scan line rather than the underlying topography. Hopefully this diagram accurately illustrates the problem:

2. There is a problem or bug with PCL's plane fitting code. This was suggested to me by a colleague who suggested that because they're all pointing upwards, it might be because that is the default and if the plane fitting functions fail, it won't produce anything different. Now, I've tracked the normal calculation code down to pcl::eigen33, where the smallest eigenvalue is found, and it's associated eigenvector is set to the nx, ny and nz normal coordiantes. But I haven't gotten any further than that. yet. This theory is the reason I'm raising the issue here and not as a general issue on the mailing list.

So my question is: Which of these two theories is likely to be correct, and are there any suggestions on what I can do to resolve it?

Start by reproducing the reported normals with carpark_cloud.ply in the PCL visualizer tutorial, then inspect the normal calculation path around pcl::eigen33. Compare the KNearest and Radius searches described in the issue and determine whether the behavior comes from sparse Velodyne data or plane fitting. Done means establishing the cause and identifying a concrete correction or limitation.