M3C2 projection cylinders - overlapping?

[claireearlie]

Hi Dimitri/Daniel/Cloud Compare community!
Does anyone know if and by how much the projection cylinders in the M3C2 cloud comparison algorithm overlap? I am trying to calculate surface volume change, but am in fear of overestimating if the diameter of the projection cylinder overlaps along the surface of the cliff. At the moment I am multiplying the distance by the cylinder diameter, by the number of cylinders..any ideas anyone?
Regards
Claire

[daniel]

Maybe Dimitri will post a comment on this later, but as he is currently in NZ I guess he won't reply very soon.

In Nicolas Brodu's version of the algorithm, if you don't set the 'cylinder_base' parameter yourself, I believe the smallest 'normal scale' is used as diameter for the cylinders.

So if you have an estimation of the density of your point cloud, you could roughly estimate the surface 'per point'. Here's the way I'd do this: in the latest 'beta' version of CloudCompare, there's a new method to compute an accurate estimation of the density (see 'Tools > Other > Density > Accurate'). Let Dv be the density at a given point (the density is in 'number of points' per volume unit). If you admit that the cloud is locally flat, then you can replace the sphere volume (4/3*pi*r^3) by the disc area (pi*r^2). Therefore the 'surface' density would be something like Dis ~ 3/4*Div (as r = 1). Eventually you get the surface per point: Si = 1/Dis. By multiplying Si by the ith point distance (i.e. the cylinder 'height') and summing that for all points you'll get an estimation of the volume change. You can do most of the job (but the final summation) with the 'Edit > Scalar Fields > Arithmetic' and 'Edit > Scalar Fields > Add constant SF' tools.

However this is maybe a bit too much complicated (and sensitive to noise). It may be easier to regularly sub-sample the cloud at a known density (see the 'Edit > Subsample' tool - with the 'space' method) and use this cloud as 'core' points for M3C2 computation. This way you'll only have to multiply the number of core points per the sum of their distances (multiplied by the mean cylinder base surface - I'll let you choose what is the best value depending on the minimum distance between points as this is what you'll input in the 'Subsample' tool).

Daniel

[claireearlie]

Many thanks for your reply Daniel. I have taken the second approach in my method and sub-sampled the point cloud to use the core point file for computation. To clarify, if I have subsampled at 10cm spacing and used a projection scale of 0.3m. To calculate my total volume change, I have multiplied the area of the cylinder base (pi*r^2 (r being 0.5*projection scale)) by the distances. Is this correct or do I need to account for overlap of cylinders at all?
Regards
Claire

[daniel]

The 'projection scale' is used to extract neighbors and fit a plane on them (in order to get a robust estimation of the mean distance). So it seems rather valid to estimate the 'mean cylinder' volume by multiplying the surface of its section by its height (the M3C2 distance). But with a diameter 3 times larger than the core points sampling, there's clearly a huge overlap. You must clearly account for it.

The easiest idea would be to divide the result by 9 (i.e. 30^2/10^2) considering that you get cylinders with a section 9 times wider than the minimal empty area around each core point. So It would be equivalent to consider directly the 10 cm spacing as base 'diameter'. But in this case we see more clearly that we miss the mass in-between the cylinders. It's hard to estimate how much precisely... maybe you could consider 'squared' cylinders instead of circular ones (i.e. S = 4*pi*r^2 instead of 3.14). The truth is probably in between ;)

[claireearlie]

Thanks Daniel. I completely overlooked how much the cylinders would overlap. Quite significantly. No wonder I was over-estimating! Comparing the volumes from a) dividing the result by 9 and b) applying a smaller projection scale (in this case 10cm) gives very similar results, to within 10 cubic metres. The problem with the latter option is firstly the missing data between the cylinders and also the limitation of a confident surface change with a significantly reduced number of points in the cylinder in the corresponding cloud. The first solution, still accounts for the accurate distance computation yet removing the percentage of the data that overlaps.
Would you agree this is robust enough for a volume difference?
Cheers!
Claire

[daniel]

Oh I was only suggesting to compute the volume with cylinders of diameter 10 cm instead of 30 cm (not to change the projection scale). You should definitely keep the 30 cm for M3C2 distances computation (as this is much more robust as you pointed out).

It was a bit twisted (as I was thinking while writing my answer) but my '10 cm' version was only here to emphasize that the missing matter was present in both cases (i.e. dividing by 9 or using directly in your computation a radius of 10 cm is exactly the same). So some mass is missing in all cases (this is why taking a 'squared' section cylinder would give a tighter version - maybe slightly overestimated - and the right answer should lie in between).

And now that I'm thinking about it, there's the issue of normals: by default they corresponds to the local surface normal. So in planar areas there's no problem, all the cylinders are sitting "straight", next to each other. But in curvy areas, the cylinders will likely intersect with their neighbors... Maybe constraining the normals to 'pure' vertical ones (I believe this option exists in Brodu's code) and orienting the cloud so that the surface is globally horizontal would do the trick? (or at least you could estimate the influence of this parameter on the result).

[azmann]

This method for volume calculation makes sense to me except for one thing. How do you know or where do you find the number of points of each value (what would be the height for the cylinder volume calculation)? Is there some box I'm missing that saves all of the signed differences in a file?
Thanks.
Aaron

[daniel]

Well if I'm not mistaken the height of the cylinder is the distance computed by the qM3C2 algorithm. So you just have to export the output cloud (core points with distances) as an ASCII file typically, then run a little script in Matlab (or even Excel if you don't have too much core points) to do the calculation.

To help you, there's also the not yet documented/validated method "Tools > Sand box (research) > Export cloud(s) info" (you have to select the output cloud to call it).

It will export for all selected clouds various pieces of information:

• cloud name
• number of points
• barycenter X
• barycenter Y
• barycenter Z

And for each scalar field:

• name
• number of (valid) values
• mean value
• std. deviation
• sum of all values

So the volume is roughly the sum of all distances/height values, multiplied by the number of valid values, multiplied by the cylinders area.

[azmann]

Yeah... I got the conceptual "how to" for calculating the volumes. I was hoping there was a way to do it outside of MATLAB as I don't know it, and my point clouds are in the 300-500 million points range, meaning too large for excel.
Thanks though

[daniel]

With the second method I proposed you should be able to do it with a simple calculator ;)