Estimating the missing points of a 3D point cloud

Question

Consider a cloud of N points (forming a smooth 3D object), in which n points are missing. Also, consider that there is no prior knowledge about the original shape of the point cloud. The only information available is the cloud of (N - n) points.

1) Compared to total points N , how much information do the missing points carry? Does it rely on the density and distribution of the points? what is the math behind that?

2) How can one estimate the missing points? Under what distribution of n, and what ratio of n and N, is this estimation possible?

Answer 1

(1) I'm not sure if there is a general answer to that. I think the "amount of information" of each point depends a lot on the actual object in question.

For example: For 100 points, all lying in a plane, each individual point carries almost no information. You could take away dozens of them, and the object would effectively still be the same. But for 4 points in a tetrahedronal constellation, taking away just one single point would turn the remaining points into a plane ($\rightarrow $ loss of a local feature).

Therefore, it is important that the sampling frequency is high enough compared to the frequency of local features that you want to retain (cf. Nyquist–Shannon sampling theorem). Take into account that your effective sampling frequency is lowered due to the missing points. By how much? That depends on the distribution of said points, e.g. every 100th point versus huge local clusters.

(2) You could reconstruct the surface and take the missing points from the reconstruction. That's a complex topic, so here is a quick summary of one way to do that: Use the points to define an implicit function for the surface using moving least squares. Then use marching cubes to create a mesh of the surface and maybe apply some smoothing.

Answer 2

We could only call the points "missing" with respect to our model (the surface in your case) not w.r.t the point cloud itself. As far as the point cloud is concerned, individual points can be anywhere.

However, we can only simulate the missing points by sampling our model, the interpolant. This of course doesn't add any new essential information: what's missing is missing.

The math behind this is called the scattered data interpolation, a topic in the approximation theory. The smoothest interpolant (a function that minimizes a certain "energy" integral) is often written as a radial basis function.

For example, univariate piecewise linear and cubic interpolations can be written as an RBF sum where each coefficient ($c_i$) is proportional to the variation of estimated slopes (or the 3rd derivatives, correspondingly). So, if the coefficient is small, i.e., there is little change in slope, the point is actually not adding much information above our underlying model and could be dropped and resampled later if needed from the model function.