Let's say we have an unorganized point cloud P1 with N points, each with coordinates {x,y,z}. We apply non-rigid transformation to P1 (translation + rotation + warping), to obtain point cloud P2. Given a pair of corresponding points in P1 and P2, how can we efficiently estimate the change in local point density around this point without performing explicit meshing? In other words, how to estimate the local space compression/expansion around each point after the transformation? Consider that the expansion/compression may not be isotropic.


If you wish to know only the change in density you are interested in the dilatation or volumetric strain of the stress tensor associated with the transformation.

If you also wish to know about the anisotropy of the stretching you should look at computing the right Cauchy-Green deformation tensor, $\Delta$, and it's associated eigenvalues and eigenvectors. The eigenvectors of this tensor define the primary axes of deformation and the eigenvalues are equal to the squares of the stretching ratios along these axes. The density ratio is given by the square root of the determinant of $\Delta$ which equals the square root of the eigenvalues: $\rho_2/\rho_1 = \sqrt{\det(\Delta)}= \sqrt{\lambda_1 \lambda_2 \lambda_3}$.

To do these computations you will need to compute (or at least estimate) the derivatives of your transformation. If you can do this analytically then the problem is easy. If not, the simplest way to compute the relevant tensors for these quantities is to perform the transformation on 6 additional points in a stencil around each point in your cloud and then use those to compute a finite difference approximation of the terms in the stress/deformation tensor. This is often done to compute the Cauchy-Green deformation tensor for computing Lagrangian coherent structures (LCS) for fluid flow analysis. If central differences are used this method is second order accurate in the stencil size, but quickly loses accuracy if the deformations are large enough that the transformation is not approximately linear on the scale of the stencil.

If you are not able to perform the transformation on arbitrary points you can use the points you know to estimate the deformation tensor. The simplest method involves choosing N neighbors of a given point and using those to estimate the deformation tensor. This can be formulated as a least-squares problem to determine the components of a 3x3 transformation matrix, $\Phi$, such that $\Phi~(\text{P}1_i-\text{P}1_0) = (\text{P}2_i-\text{P}2_0)$ where subscript $0$ denotes the point of interest and $i$ denotes the neighbors. In 3D you will need a minimum of 3 neighbors to determine $\Phi$ (3 points x 3 components {x,y,z} gives 9 linear equations for the 9 entries in $\Phi$). The deformation tensor is then given by $\Delta = \Phi^\intercal \Phi$. This method is first order accurate in the point spacing and quickly loses accuracy when the points are far enough apart so that the transformation is not locally linear on the neighborhood being used. If my memory is correct, this is the method that is used for computing the deformation tensor to find LCS on unstructured meshes in this paper. As a side note, this method is provably equivalent to using centered finite differences (and recovers second order accuracy) if the you use 6 neighbors at the locations of the points in the finite difference stencil.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.