Shrinkwrap: new mode that projects along the target normal.

The Nearest Surface Point shrink method, while fast, is neither
smooth nor continuous: as the source point moves, the projected
point can both stop and jump. This causes distortions in the
deformation of the shrinkwrap modifier, and the motion of an
animated object with a shrinkwrap constraint.

This patch implements a new mode, which, instead of using the simple
nearest point search, iteratively solves an equation for each triangle
to find a point which has its interpolated normal point to or from the
original vertex. Non-manifold boundary edges are treated as infinitely
thin cylinders that cast normals in all perpendicular directions.

Since this is useful for the constraint, and having multiple
objects with constraints targeting the same guide mesh is a quite
reasonable use case, rather than calculating the mesh boundary edge
data over and over again, it is precomputed and cached in the mesh.

Reviewers: mont29

Differential Revision: https://developer.blender.org/D3836

1 files changed, 9 insertions, 0 deletions

diff --git a/source/blender/blenlib/BLI_math_solvers.h b/source/blender/blenlib/BLI_math_solvers.h
index 4352779d9ee..845d2100133 100644
--- a/source/blender/blenlib/BLI_math_solvers.h
+++ b/source/blender/blenlib/BLI_math_solvers.h
@@ -53,6 +53,15 @@ void BLI_svd_m3(const float m3[3][3], float r_U[3][3], float r_S[], float r_V[3]
 bool BLI_tridiagonal_solve(const float *a, const float *b, const float *c, const float *d, float *r_x, const int count);
 bool BLI_tridiagonal_solve_cyclic(const float *a, const float *b, const float *c, const float *d, float *r_x, const int count);
 
+/* Generic 3 variable Newton's method solver. */
+typedef void (*Newton3D_DeltaFunc)(void *userdata, const float x[3], float r_delta[3]);
+typedef void (*Newton3D_JacobianFunc)(void *userdata, const float x[3], float r_jacobian[3][3]);
+typedef bool (*Newton3D_CorrectionFunc)(void *userdata, const float x[3], float step[3], float x_next[3]);
+
+bool BLI_newton3d_solve(
+        Newton3D_DeltaFunc func_delta, Newton3D_JacobianFunc func_jacobian, Newton3D_CorrectionFunc func_correction, void *userdata,
+        float epsilon, int max_iterations, bool trace, const float x_init[3], float result[3]);
+
 #ifdef BLI_MATH_GCC_WARN_PRAGMA
 #  pragma GCC diagnostic pop
 #endif