# Local Coordinates of Deformed Lattice

I'm making a lattice based volume FFD and I'm having trouble with gaps in my data resulting from doing a typical deformer. I think I need to go through the voxels in the deformed lattice and then find the corresponding undeformed coordinate, that is, go from having the deformed position to getting the local (s,t,u) coordinate that was deformed to that position and then write the interpolated value of the original voxel. This is obviously the opposite way of doing a lattice based FFD with vector valued trivariate Bernstein polynomials.

I am struggling to figure out a way to get the local coordinates of a point in the deformed volume. If anyone has any advice it would be much appreciated.

Thank you!

• Could you please add a small screenshot of the gaps? I can't imagine what you mean by gaps from a typical deformer. Commented May 26, 2020 at 10:51

Maybe something quick (to set up, no guarantees of actual speed) and dirty.

Whatever your method was, it probably boiled down to a vector function \begin{align} \begin{bmatrix} x,\, y,\, z\end{bmatrix} = F\Big([s,\, t,\, u] \,\, \Big| \,\, V_{ijk} \, : i,j,k = 1..N\Big) \end{align} where $$V_{ijk} \in \mathbb{R}^3$$are the vertices of the three dimensional lattice.

Basically, you currently have the new coordinates $$[x,\, y,\, z]$$ of a point, and you want to find the original ones $$[s,\, t,\, u]$$. I hope you still have the coordinates of the lattice vertices $$V_{ijk}$$. To retrieve the initial coordinates $$[s,\, t,\, u]$$ you have to solve for $$[s,\, t,\, u]$$ the system of equations \begin{align} \begin{bmatrix} x,\, y,\, z\end{bmatrix} = F\Big([s,\, t,\, u] \,\, \Big| \,\, V_{ijk} \, : i,j,k = 1..N\Big) \end{align} where $$[x,\, y,\, z]$$ is given and the points $$V_{ijk}$$ are given For simplicity, I am going to write $$\begin{bmatrix} x,\, y,\, z\end{bmatrix} = F\big([s,\, t,\, u] \,\, \big| \,\, V \,\big)$$ To solve it, use a type of Newton's method. Set a small enough number $$h$$.

Set your initial $$s_0=x, t_0=y, u_0=z$$ and set up your error equal to $$err = 1$$ (or whatever).

While $$err \geq h^2$$ execute the following iteration:

1. Assume you have a current approximation $$[s_n,\, t_n,\, u_n]$$;

2. Calculate the following three three-vector (as rows) \begin{align} &\Delta_s F_n = \frac{1}{h} \Big( \, F\big([s_n+h,\, t_n,\, u_n] \,\, \big| \,\, V \,\big) - F\big([s_n,\, t_n,\, u_n] \,\, \Big| \,\, V \,\big) \, \Big)\\ &\Delta_t F_n = \frac{1}{h} \Big( \, F\big([s_n,\, t_n+h,\, u_n] \,\, \big| \,\, V \,\big) - F\big([s_n,\, t_n,\, u_n] \,\, \Big| \,\, V \,\big) \, \Big)\\ &\Delta_u F_n = \frac{1}{h} \Big( \, F\big([s_n,\, t_n,\, u_n+h] \,\, \big| \,\, V \,\big) - F\big([s_n,\, t_n,\, u_n] \,\, \Big| \,\, V \,\big) \, \Big) \end{align}

3. Set the following three by three matrix $$M_n = \begin{bmatrix} \Delta_s F_n \\ \Delta_t F_n \\ \Delta_u F_n\end{bmatrix}$$ (the vectors are the ones computed above but transposed and are therefore vector-columns);

4. Calculate the inverse matrix $$M_n^{-1}$$;

5. Calculate the update $$[s_{n+1},\, t_{n+1},\, u_{n+1}] = [s_n,\, t_n,\, u_n] + \Big(\,[x,\, y,\, z] - F\big([s_n,\, t_n,\, u_n] \,\, \Big| \,\, V \,\big)\,\Big)\, M_n^{-1}$$ (all of this is written as vector matrix multiplication, where you are working with $$1 \times 3$$ row-vectors and multiplying such$$1 \times 3$$ row-vectors with the $$3 \times 3$$ matrix $$M_n^{-1}$$ on the right)

6. Calculate the error $$err = \Big\|\, [x,\, y,\, z] - F\big([s_{n+1},\, t_{n+1},\, u_{n+1}] \,\, \Big| \,\, V \,\big)\, \Big\|^2$$

7. Go back to the beginning of the iteration to check whether $$err \geq h^2$$

The result of this iteration is an approximation of the coordinates $$[s,\, t,\, u]$$. I hope this works.