Convex Hull calculation in Point Cloud Library fails in 2 as well as 3 dimensions

Question

i'm following the tutorial of the PCL docs for calculating a 2D Convex Hull see here.

I have a cloud and some indices, project them on a plane with given coefficients and then calculate the convex hull. Here's the code:

PointCloud<PointXYZ>::Ptr tmpInliers(new PointCloud<PointXYZ>());

ProjectInliers<PointXYZ> proj;
proj.setModelType(SACMODEL_PLANE);
proj.setInputCloud(someCloud); 
proj.setIndices(someIndices); 
proj.setModelCoefficients(someCoefficients);
proj.filter(*tmpInliers);

PointCloud<PointXYZ>::Ptr hull(new PointCloud<PointXYZ>());
ConvexHull<PointXYZ> chull;
chull.setInputCloud(tmpInliers);
chull.setComputeAreaVolume(true);
chull.setDimension(3); <--- see below
chull.reconstruct(*hull);

The results i get for the total area and volume are around:

  Area & Volume of convex hull: 7.8726e-312 2.122e-314

For values of tmpInliers ranging around

(-0.80562,-0.787018,2.25184)
(-0.477351,-0.798953,2.11432)
(-0.633823,-0.750283,2.96717)
[....]

If i change "setDimensions" to "2" i get the following error

[pcl::ConvexHull::performReconstrution2D] ERROR: qhull was unable to compute a convex hull for the given point cloud (size of cloud)!

In the following example i am constructing a example and fail in every case (setDimension set to 2 or 3) with one of the failures from before (either "qhull was unable..." or a strange result according to values from the ConvexHull.

PointCloud<PointXYZ>::Ptr hugeBox(new PointCloud<PointXYZ>());
hugeBox->push_back(PointXYZ(10, 10, 10));
hugeBox->push_back(PointXYZ(10, 10, -10));
hugeBox->push_back(PointXYZ(10, -10, 10));
hugeBox->push_back(PointXYZ(10, -10, -10));
hugeBox->push_back(PointXYZ(-10, 10, 10));
hugeBox->push_back(PointXYZ(-10, 10, -10));
hugeBox->push_back(PointXYZ(-10, -10, 10));
hugeBox->push_back(PointXYZ(-10, -10, -10));

// Project inliers onto plane model
PointCloud<PointXYZ>::Ptr hugePlane(new PointCloud<PointXYZ>());
ProjectInliers<PointXYZ> proj;
proj.setModelType(SACMODEL_PLANE);
proj.setInputCloud(hugeBox);
proj.setModelCoefficients(coefficients);
proj.filter(*hugePlane);

// get the convex hull of plane
vector<Vertices> polygonsOut;
PointCloud<PointXYZ>::Ptr hugeHull(new PointCloud<PointXYZ>());
ConvexHull<PointXYZ> chull;
chull.setInputCloud(hugePlane);
chull.setDimension(2);
chull.reconstruct(*hugeHull, polygonsOut);

I'm a little stuck here. Why does it fail if i set it to 2 dimensions? And if i set it to 3 dimensions i occasionaly the following warning:

qhull precision warning: 
The initial hull is narrow (cosine of min. angle is 0.9999999999999991).
A coplanar point may lead to a wide facet.

I understand that this is the case if i have a planar projection, but how to avoid this?

Answer 1

Ok the problem was that PCL was linking to an old libqhull (v0.5) from the system instead to the newer v0.6 which was present but not correctly linked. Problems do not occur regularly but in some special cases with the old version, like if you have a planar projection from 3d to 2d and try to put a hull around it.

I will submit a request to the pcl-people to add a requirement for the version number.

Answer 2

I don't know the framework you are using, but let me have a guess: You are projecting the points on a plane embedded in a 3-dimensional volume, am I right? It's quite straightforward that the 3-dimensional convex hull algorithm fails, because the points projected on the plane are coplanar - by definition. Other way round, even if they are projected on the plane, which is embedded in a 3-dimensional space, the points reside in an 3-dimensional space, too - I guess. The 2-d convex hull algorithm on the other hand expects real 2-dimensional points - most likely. Thus, I think it'll do reducing the projected points to a real 2-dimensional space by means of some sort of mapping and then apply the 2-d convex hull algorith.

Answer 3

I had the same problem, but after putting the data on PCL_VIEWER, it showed the point cloud as a set of parallel lines, so when I manipulated the planar projection, the original data became planar lines, and ConvelHull Algorithm could not accept such an input, and I still did not solve it.