Fix T81707: Spline IK Joints "Floating" above curve

The issue was that where_on_path uses a resampled curve to get the data
from the curve. This leads to disconnects between the curve the user
sees and the evaluated location data.

To fix this we simply use the actual curve data the user can see.

The older code needed a cleanup either way as there were hacks in other
parts of the code trying to work around some brokenness. This is now
fixed and we no longer need to clamp the evaluation range to 0-1 or make
helper functions to make it do what we actually want.

Reviewed By: Campbell, Sybren

Differential Revision: http://developer.blender.org/D10898

16 files changed, 310 insertions, 350 deletions

diff --git a/source/blender/blenkernel/BKE_anim_path.h b/source/blender/blenkernel/BKE_anim_path.h
index ae2d13530ed..9db63080fd9 100644
--- a/source/blender/blenkernel/BKE_anim_path.h
+++ b/source/blender/blenkernel/BKE_anim_path.h
@@ -26,22 +26,28 @@
 extern "C" {
 #endif
 
-struct ListBase;
+struct CurveCache;
 struct Object;
-struct Path;
 
 /* ---------------------------------------------------- */
 /* Curve Paths */
 
-void free_path(struct Path *path);
-void calc_curvepath(struct Object *ob, struct ListBase *nurbs);
-bool where_on_path(const struct Object *ob,
-                   float ctime,
-                   float r_vec[4],
-                   float r_dir[3],
-                   float r_quat[4],
-                   float *r_radius,
-                   float *r_weight);
+int BKE_anim_path_get_array_size(const struct CurveCache *curve_cache);
+float BKE_anim_path_get_length(const struct CurveCache *curve_cache);
+
+/* This function populates the 'ob->runtime.curve_cache->anim_path_accum_length' data.
+ * You should never have to call this manually as it should already have been called by
+ * 'BKE_displist_make_curveTypes'. Do not call this manually unless you know what you are doing.
+ */
+void BKE_anim_path_calc_data(struct Object *ob);
+
+bool BKE_where_on_path(const struct Object *ob,
+                       float ctime,
+                       float r_vec[4],
+                       float r_dir[3],
+                       float r_quat[4],
+                       float *r_radius,
+                       float *r_weight);
 
 #ifdef __cplusplus
 }
diff --git a/source/blender/blenkernel/BKE_curve.h b/source/blender/blenkernel/BKE_curve.h
index 8381f015bee..26c9bef7d6c 100644
--- a/source/blender/blenkernel/BKE_curve.h
+++ b/source/blender/blenkernel/BKE_curve.h
@@ -50,7 +50,14 @@ typedef struct CurveCache {
   ListBase disp;
   ListBase bev;
   ListBase deformed_nurbs;
-  struct Path *path;
+  /* This array contains the accumulative length of the curve segments.
+   * So you can see this as a "total distance traveled" along the curve.
+   * The first entry is the length between point 0 and 1 while the last is the
+   * total length of the curve.
+   *
+   * Used by 'BKE_where_on_path'.
+   */
+  float *anim_path_accum_length;
 } CurveCache;
 
 /* Definitions needed for shape keys */
diff --git a/source/blender/blenkernel/intern/anim_path.c b/source/blender/blenkernel/intern/anim_path.c
index 628e54971ce..58ab5609fce 100644
--- a/source/blender/blenkernel/intern/anim_path.c
+++ b/source/blender/blenkernel/intern/anim_path.c
@@ -42,157 +42,193 @@ static CLG_LogRef LOG = {"bke.anim"};
 /* ******************************************************************** */
 /* Curve Paths - for curve deforms and/or curve following */
 
-/**
- * Free curve path data
- *
- * \note Frees the path itself!
- * \note This is increasingly inaccurate with non-uniform #BevPoint subdivisions T24633.
- */
-void free_path(Path *path)
+static int get_bevlist_seg_array_size(const BevList *bl)
 {
-  if (path->data) {
-    MEM_freeN(path->data);
+  if (bl->poly >= 0) {
+    /* Cyclic curve. */
+    return bl->nr;
   }
-  MEM_freeN(path);
+
+  return bl->nr - 1;
 }
 
-/**
- * Calculate a curve-deform path for a curve
- * - Only called from displist.c -> #do_makeDispListCurveTypes
- */
-void calc_curvepath(Object *ob, ListBase *nurbs)
+int BKE_anim_path_get_array_size(const CurveCache *curve_cache)
+{
+  BLI_assert(curve_cache != NULL);
+
+  BevList *bl = curve_cache->bev.first;
+
+  BLI_assert(bl != NULL && bl->nr > 1);
+
+  return get_bevlist_seg_array_size(bl);
+}
+
+float BKE_anim_path_get_length(const CurveCache *curve_cache)
 {
-  BevList *bl;
-  BevPoint *bevp, *bevpn, *bevpfirst, *bevplast;
-  PathPoint *pp;
-  Nurb *nu;
-  Path *path;
-  float *fp, *dist, *maxdist, xyz[3];
-  float fac, d = 0, fac1, fac2;
-  int a, tot, cycl = 0;
-
-  /* in a path vertices are with equal differences: path->len = number of verts */
-  /* NOW WITH BEVELCURVE!!! */
+  int seg_size = BKE_anim_path_get_array_size(curve_cache);
+  return curve_cache->anim_path_accum_length[seg_size - 1];
+}
 
+void BKE_anim_path_calc_data(struct Object *ob)
+{
   if (ob == NULL || ob->type != OB_CURVE) {
     return;
   }
-
-  if (ob->runtime.curve_cache->path) {
-    free_path(ob->runtime.curve_cache->path);
+  if (ob->runtime.curve_cache == NULL) {
+    CLOG_WARN(&LOG, "No curve cache!");
+    return;
   }
-  ob->runtime.curve_cache->path = NULL;
-
-  /* weak! can only use first curve */
-  bl = ob->runtime.curve_cache->bev.first;
+  /* We only use the first curve. */
+  BevList *bl = ob->runtime.curve_cache->bev.first;
   if (bl == NULL || !bl->nr) {
+    CLOG_WARN(&LOG, "No bev list data!");
     return;
   }
 
-  nu = nurbs->first;
-
-  ob->runtime.curve_cache->path = path = MEM_callocN(sizeof(Path), "calc_curvepath");
-
-  /* if POLY: last vertice != first vertice */
-  cycl = (bl->poly != -1);
+  /* Free old data. */
+  if (ob->runtime.curve_cache->anim_path_accum_length) {
+    MEM_freeN(ob->runtime.curve_cache->anim_path_accum_length);
+  }
 
-  tot = cycl ? bl->nr : bl->nr - 1;
+  /* We assume that we have at least two points.
+   * If there is less than two points in the curve,
+   * no BevList should have been generated.
+   */
+  BLI_assert(bl->nr > 1);
+
+  int seg_size = get_bevlist_seg_array_size(bl);
+
+  ob->runtime.curve_cache->anim_path_accum_length = (float *)MEM_mallocN(sizeof(float) * seg_size,
+                                                                         "calcpathdist");
+  float *len_data = ob->runtime.curve_cache->anim_path_accum_length;
+  BevPoint *bp_arr = bl->bevpoints;
+  float prev_len = 0.0f;
+  for (int i = 0; i < bl->nr - 1; i++) {
+    prev_len += len_v3v3(bp_arr[i].vec, bp_arr[i + 1].vec);
+    len_data[i] = prev_len;
+  }
 
-  path->len = tot + 1;
-  /* Exception: vector handle paths and polygon paths should be subdivided
-   * at least a factor resolution. */
-  if (path->len < nu->resolu * SEGMENTSU(nu)) {
-    path->len = nu->resolu * SEGMENTSU(nu);
+  if (bl->poly >= 0) {
+    /* Cyclic curve. */
+    len_data[seg_size - 1] = prev_len + len_v3v3(bp_arr[0].vec, bp_arr[bl->nr - 1].vec);
   }
+}
+
+static void get_curve_points_from_idx(const int idx,
+                                      BevList *bl,
+                                      bool is_cyclic,
+                                      BevPoint **r_p0,
+                                      BevPoint **r_p1,
+                                      BevPoint **r_p2,
+                                      BevPoint **r_p3)
+{
+  BLI_assert(idx >= 0);
+  BLI_assert(idx < bl->nr - 1 || (is_cyclic && idx < bl->nr));
+  BLI_assert(bl->nr > 1);
 
-  dist = (float *)MEM_mallocN(sizeof(float) * (tot + 1), "calcpathdist");
+  BevPoint *bp_arr = bl->bevpoints;
 
-  /* all lengths in *dist */
-  bevp = bevpfirst = bl->bevpoints;
-  fp = dist;
-  *fp = 0.0f;
-  for (a = 0; a < tot; a++) {
-    fp++;
-    if (cycl && a == tot - 1) {
-      sub_v3_v3v3(xyz, bevpfirst->vec, bevp->vec);
+  /* First segement. */
+  if (idx == 0) {
+    *r_p1 = &bp_arr[0];
+    if (is_cyclic) {
+      *r_p0 = &bp_arr[bl->nr - 1];
     }
     else {
-      sub_v3_v3v3(xyz, (bevp + 1)->vec, bevp->vec);
+      *r_p0 = *r_p1;
     }
 
-    *fp = *(fp - 1) + len_v3(xyz);
-    bevp++;
-  }
-
-  path->totdist = *fp;
-
-  /* the path verts  in path->data */
-  /* now also with TILT value */
-  pp = path->data = (PathPoint *)MEM_callocN(sizeof(PathPoint) * path->len, "pathdata");
+    *r_p2 = &bp_arr[1];
 
-  bevp = bevpfirst;
-  bevpn = bevp + 1;
-  bevplast = bevpfirst + (bl->nr - 1);
-  if (UNLIKELY(bevpn > bevplast)) {
-    bevpn = cycl ? bevpfirst : bevplast;
-  }
-  fp = dist + 1;
-  maxdist = dist + tot;
-  fac = 1.0f / ((float)path->len - 1.0f);
-  fac = fac * path->totdist;
-
-  for (a = 0; a < path->len; a++) {
-
-    d = ((float)a) * fac;
-
-    /* we're looking for location (distance) 'd' in the array */
-    if (LIKELY(tot > 0)) {
-      while ((fp < maxdist) && (d >= *fp)) {
-        fp++;
-        if (bevp < bevplast) {
-          bevp++;
-        }
-        bevpn = bevp + 1;
-        if (UNLIKELY(bevpn > bevplast)) {
-          bevpn = cycl ? bevpfirst : bevplast;
-        }
-      }
-
-      fac1 = (*(fp)-d) / (*(fp) - *(fp - 1));
-      fac2 = 1.0f - fac1;
+    if (bl->nr > 2) {
+      *r_p3 = &bp_arr[2];
     }
     else {
-      fac1 = 1.0f;
-      fac2 = 0.0f;
+      *r_p3 = *r_p2;
     }
+    return;
+  }
 
-    interp_v3_v3v3(pp->vec, bevp->vec, bevpn->vec, fac2);
-    pp->vec[3] = fac1 * bevp->tilt + fac2 * bevpn->tilt;
-    pp->radius = fac1 * bevp->radius + fac2 * bevpn->radius;
-    pp->weight = fac1 * bevp->weight + fac2 * bevpn->weight;
-    interp_qt_qtqt(pp->quat, bevp->quat, bevpn->quat, fac2);
-    normalize_qt(pp->quat);
+  /* Last segment (or next to last in a cyclic curve). */
+  if (idx == bl->nr - 2) {
+    /* The case when the bl->nr == 2 falls in to the "first segement" check above.
+     * So here we can assume that bl->nr > 2.
+     */
+    *r_p0 = &bp_arr[idx - 1];
+    *r_p1 = &bp_arr[idx];
+    *r_p2 = &bp_arr[idx + 1];
+
+    if (is_cyclic) {
+      *r_p3 = &bp_arr[0];
+    }
+    else {
+      *r_p3 = *r_p2;
+    }
+    return;
+  }
 
-    pp++;
+  if (idx == bl->nr - 1) {
+    /* Last segment in a cyclic curve. This should only trigger if the curve is cyclic
+     * as it gets an extra segment between the end and the start point. */
+    *r_p0 = &bp_arr[idx - 1];
+    *r_p1 = &bp_arr[idx];
+    *r_p2 = &bp_arr[0];
+    *r_p3 = &bp_arr[1];
+    return;
   }
 
-  MEM_freeN(dist);
+  /* To get here the curve has to have four curve points or more and idx can't
+   * be the first or the last segment.
+   * So we can assume that we can get four points without any special checks.
+   */
+  *r_p0 = &bp_arr[idx - 1];
+  *r_p1 = &bp_arr[idx];
+  *r_p2 = &bp_arr[idx + 1];
+  *r_p3 = &bp_arr[idx + 2];
 }
 
-static int interval_test(const int min, const int max, int p1, const int cycl)
+static bool binary_search_anim_path(const float *accum_len_arr,
+                                    const int seg_size,
+                                    const float goal_len,
+                                    int *r_idx,
+                                    float *r_frac)
 {
-  if (cycl) {
-    p1 = mod_i(p1 - min, (max - min + 1)) + min;
-  }
-  else {
-    if (p1 < min) {
-      p1 = min;
+  float left_len, right_len;
+  int cur_idx = 0, cur_base = 0;
+  int cur_step = seg_size - 1;
+
+  while (true) {
+    cur_idx = cur_base + cur_step / 2;
+    left_len = accum_len_arr[cur_idx];
+    right_len = accum_len_arr[cur_idx + 1];
+
+    if (left_len <= goal_len && right_len > goal_len) {
+      *r_idx = cur_idx + 1;
+      *r_frac = (goal_len - left_len) / (right_len - left_len);
+      return true;
     }
-    else if (p1 > max) {
-      p1 = max;
+    if (cur_idx == 0) {
+      /* We ended up at the first segement. The point must be in here. */
+      *r_idx = 0;
+      *r_frac = goal_len / accum_len_arr[0];
+      return true;
     }
+
+    if (UNLIKELY(cur_step == 0)) {
+      /* This should never happen unless there is something horribly wrong. */
+      CLOG_ERROR(&LOG, "Couldn't find any valid point on the animation path!");
+      BLI_assert(!"Couldn't find any valid point on the animation path!");
+      return false;
+    }
+
+    if (left_len < goal_len) {
+      /* Go to the right. */
+      cur_base = cur_idx + 1;
+      cur_step--;
+    } /* Else, go to the left. */
+
+    cur_step /= 2;
   }
-  return p1;
 }
 
 /**
@@ -203,66 +239,70 @@ static int interval_test(const int min, const int max, int p1, const int cycl)
  *
  * \return success.
  */
-bool where_on_path(const Object *ob,
-                   float ctime,
-                   float r_vec[4],
-                   float r_dir[3],
-                   float r_quat[4],
-                   float *r_radius,
-                   float *r_weight)
+bool BKE_where_on_path(const Object *ob,
+                       float ctime,
+                       float r_vec[4],
+                       float r_dir[3],
+                       float r_quat[4],
+                       float *r_radius,
+                       float *r_weight)
 {
-  Curve *cu;
-  const Nurb *nu;
-  const BevList *bl;
-  const Path *path;
-  const PathPoint *pp, *p0, *p1, *p2, *p3;
-  float fac;
-  float data[4];
-  int cycl = 0, s0, s1, s2, s3;
-  const ListBase *nurbs;
-
   if (ob == NULL || ob->type != OB_CURVE) {
     return false;
   }
-  cu = ob->data;
-  if (ob->runtime.curve_cache == NULL || ob->runtime.curve_cache->path == NULL ||
-      ob->runtime.curve_cache->path->data == NULL) {
-    CLOG_WARN(&LOG, "no path!");
-    return false;
-  }
-  path = ob->runtime.curve_cache->path;
-  pp = path->data;
-
-  /* test for cyclic */
-  bl = ob->runtime.curve_cache->bev.first;
-  if (!bl) {
+  Curve *cu = ob->data;
+  if (ob->runtime.curve_cache == NULL) {
+    CLOG_WARN(&LOG, "No curve cache!");
     return false;
   }
-  if (!bl->nr) {
+  /* We only use the first curve. */
+  BevList *bl = ob->runtime.curve_cache->bev.first;
+  if (bl == NULL || !bl->nr) {
+    CLOG_WARN(&LOG, "No bev list data!");
     return false;
   }
-  if (bl->poly > -1) {
-    cycl = 1;
+
+  /* Test for cyclic curve. */
+  const bool is_cyclic = bl->poly >= 0;
+
+  if (is_cyclic) {
+    /* Wrap the time into a 0.0 - 1.0 range. */
+    if (ctime < 0.0f || ctime > 1.0f) {
+      ctime -= floorf(ctime);
+    }
   }
 
-  /* values below zero for non-cyclic curves give strange results */
-  BLI_assert(cycl || ctime >= 0.0f);
+  /* The curve points for this ctime value. */
+  BevPoint *p0, *p1, *p2, *p3;
 
-  ctime *= (path->len - 1);
+  float frac;
+  const int seg_size = get_bevlist_seg_array_size(bl);
+  float *accum_len_arr = ob->runtime.curve_cache->anim_path_accum_length;
+  const float goal_len = ctime * accum_len_arr[seg_size - 1];
 
-  s1 = (int)floor(ctime);
-  fac = (float)(s1 + 1) - ctime;
+  /* Are we simply trying to get the start/end point? */
+  if (ctime <= 0.0f || ctime >= 1.0f) {
+    const float clamp_time = clamp_f(ctime, 0.0f, 1.0f);
+    const int idx = clamp_time * (seg_size - 1);
+    get_curve_points_from_idx(idx, bl, is_cyclic, &p0, &p1, &p2, &p3);
 
-  /* path->len is corrected for cyclic */
-  s0 = interval_test(0, path->len - 1 - cycl, s1 - 1, cycl);
-  s1 = interval_test(0, path->len - 1 - cycl, s1, cycl);
-  s2 = interval_test(0, path->len - 1 - cycl, s1 + 1, cycl);
-  s3 = interval_test(0, path->len - 1 - cycl, s1 + 2, cycl);
+    if (idx == 0) {
+      frac = goal_len / accum_len_arr[0];
+    }
+    else {
+      frac = (goal_len - accum_len_arr[idx - 1]) / (accum_len_arr[idx] - accum_len_arr[idx - 1]);
+    }
+  }
+  else {
+    /* Do binary search to get the correct segment. */
+    int idx;
+    bool found_idx = binary_search_anim_path(accum_len_arr, seg_size, goal_len, &idx, &frac);
 
-  p0 = pp + s0;
-  p1 = pp + s1;
-  p2 = pp + s2;
-  p3 = pp + s3;
+    if (UNLIKELY(!found_idx)) {
+      return false;
+    }
+    get_curve_points_from_idx(idx, bl, is_cyclic, &p0, &p1, &p2, &p3);
+  }
 
   /* NOTE: commented out for follow constraint
    *
@@ -272,65 +312,68 @@ bool where_on_path(const Object *ob,
    */
   // if (cu->flag & CU_FOLLOW) {
 
-  key_curve_tangent_weights(1.0f - fac, data, KEY_BSPLINE);
+  float w[4];
+
+  key_curve_tangent_weights(frac, w, KEY_BSPLINE);
 
-  interp_v3_v3v3v3v3(r_dir, p0->vec, p1->vec, p2->vec, p3->vec, data);
+  interp_v3_v3v3v3v3(r_dir, p0->vec, p1->vec, p2->vec, p3->vec, w);
 
   /* Make compatible with #vec_to_quat. */
   negate_v3(r_dir);
   //}
 
-  nurbs = BKE_curve_editNurbs_get(cu);
+  const ListBase *nurbs = BKE_curve_editNurbs_get(cu);
   if (!nurbs) {
     nurbs = &cu->nurb;
   }
-  nu = nurbs->first;
+  const Nurb *nu = nurbs->first;
 
   /* make sure that first and last frame are included in the vectors here  */
-  if (nu->type == CU_POLY) {
-    key_curve_position_weights(1.0f - fac, data, KEY_LINEAR);
+  if (ELEM(nu->type, CU_POLY, CU_BEZIER, CU_NURBS)) {
+    key_curve_position_weights(frac, w, KEY_LINEAR);
   }
-  else if (nu->type == CU_BEZIER) {
-    key_curve_position_weights(1.0f - fac, data, KEY_LINEAR);
-  }
-  else if (s0 == s1 || p2 == p3) {
-    key_curve_position_weights(1.0f - fac, data, KEY_CARDINAL);
+  else if (p2 == p3) {
+    key_curve_position_weights(frac, w, KEY_CARDINAL);
   }
   else {
-    key_curve_position_weights(1.0f - fac, data, KEY_BSPLINE);
+    key_curve_position_weights(frac, w, KEY_BSPLINE);
   }
 
   r_vec[0] = /* X */
-      data[0] * p0->vec[0] + data[1] * p1->vec[0] + data[2] * p2->vec[0] + data[3] * p3->vec[0];
+      w[0] * p0->vec[0] + w[1] * p1->vec[0] + w[2] * p2->vec[0] + w[3] * p3->vec[0];
   r_vec[1] = /* Y */
-      data[0] * p0->vec[1] + data[1] * p1->vec[1] + data[2] * p2->vec[1] + data[3] * p3->vec[1];
+      w[0] * p0->vec[1] + w[1] * p1->vec[1] + w[2] * p2->vec[1] + w[3] * p3->vec[1];
   r_vec[2] = /* Z */
-      data[0] * p0->vec[2] + data[1] * p1->vec[2] + data[2] * p2->vec[2] + data[3] * p3->vec[2];
+      w[0] * p0->vec[2] + w[1] * p1->vec[2] + w[2] * p2->vec[2] + w[3] * p3->vec[2];
+
+  /* Clamp weights to 0-1 as we don't want to extrapolate other values than position. */
+  clamp_v4(w, 0.0f, 1.0f);
+
   r_vec[3] = /* Tilt, should not be needed since we have quat still used */
-      data[0] * p0->vec[3] + data[1] * p1->vec[3] + data[2] * p2->vec[3] + data[3] * p3->vec[3];
+      w[0] * p0->tilt + w[1] * p1->tilt + w[2] * p2->tilt + w[3] * p3->tilt;
 
   if (r_quat) {
     float totfac, q1[4], q2[4];
 
-    totfac = data[0] + data[3];
+    totfac = w[0] + w[3];
     if (totfac > FLT_EPSILON) {
-      interp_qt_qtqt(q1, p0->quat, p3->quat, data[3] / totfac);
+      interp_qt_qtqt(q1, p0->quat, p3->quat, w[3] / totfac);
     }
     else {
       copy_qt_qt(q1, p1->quat);
     }
 
-    totfac = data[1] + data[2];
+    totfac = w[1] + w[2];
     if (totfac > FLT_EPSILON) {
-      interp_qt_qtqt(q2, p1->quat, p2->quat, data[2] / totfac);
+      interp_qt_qtqt(q2, p1->quat, p2->quat, w[2] / totfac);
     }
     else {
       copy_qt_qt(q2, p3->quat);
     }
 
-    totfac = data[0] + data[1] + data[2] + data[3];
+    totfac = w[0] + w[1] + w[2] + w[3];
     if (totfac > FLT_EPSILON) {
-      interp_qt_qtqt(r_quat, q1, q2, (data[1] + data[2]) / totfac);
+      interp_qt_qtqt(r_quat, q1, q2, (w[1] + w[2]) / totfac);
     }
     else {
       copy_qt_qt(r_quat, q2);
@@ -338,13 +381,11 @@ bool where_on_path(const Object *ob,
   }
 
   if (r_radius) {
-    *r_radius = data[0] * p0->radius + data[1] * p1->radius + data[2] * p2->radius +
-                data[3] * p3->radius;
+    *r_radius = w[0] * p0->radius + w[1] * p1->radius + w[2] * p2->radius + w[3] * p3->radius;
   }
 
   if (r_weight) {
-    *r_weight = data[0] * p0->weight + data[1] * p1->weight + data[2] * p2->weight +
-                data[3] * p3->weight;
+    *r_weight = w[0] * p0->weight + w[1] * p1->weight + w[2] * p2->weight + w[3] * p3->weight;
   }
 
   return true;
diff --git a/source/blender/blenkernel/intern/armature_update.c b/source/blender/blenkernel/intern/armature_update.c
index 8f74b8ff054..475b64cb9b3 100644
--- a/source/blender/blenkernel/intern/armature_update.c
+++ b/source/blender/blenkernel/intern/armature_update.c
@@ -229,7 +229,7 @@ static bool splineik_evaluate_init(tSplineIK_Tree *tree, tSplineIk_EvalState *st
 
   CurveCache *cache = ikData->tar->runtime.curve_cache;
 
-  if (ELEM(NULL, cache, cache->path, cache->path->data)) {
+  if (ELEM(NULL, cache, cache->anim_path_accum_length)) {
     return false;
   }
 
@@ -242,7 +242,7 @@ static bool splineik_evaluate_init(tSplineIK_Tree *tree, tSplineIk_EvalState *st
   if ((ikData->yScaleMode != CONSTRAINT_SPLINEIK_YS_FIT_CURVE) && (tree->totlength != 0.0f)) {
     /* get the current length of the curve */
     /* NOTE: this is assumed to be correct even after the curve was resized */
-    float splineLen = cache->path->totdist;
+    const float splineLen = BKE_anim_path_get_length(cache);
 
     /* calculate the scale factor to multiply all the path values by so that the
      * bone chain retains its current length, such that
@@ -297,7 +297,7 @@ static void splineik_evaluate_bone(
     }
 
     /* tail endpoint */
-    if (where_on_path(ikData->tar, pointEnd, vec, dir, NULL, &rad, NULL)) {
+    if (BKE_where_on_path(ikData->tar, pointEnd, vec, dir, NULL, &rad, NULL)) {
       /* apply curve's object-mode transforms to the position
        * unless the option to allow curve to be positioned elsewhere is activated (i.e. no root)
        */
@@ -314,7 +314,7 @@ static void splineik_evaluate_bone(
     }
 
     /* head endpoint */
-    if (where_on_path(ikData->tar, pointStart, vec, dir, NULL, &rad, NULL)) {
+    if (BKE_where_on_path(ikData->tar, pointStart, vec, dir, NULL, &rad, NULL)) {
       /* apply curve's object-mode transforms to the position
        * unless the option to allow curve to be positioned elsewhere is activated (i.e. no root)
        */
diff --git a/source/blender/blenkernel/intern/constraint.c b/source/blender/blenkernel/intern/constraint.c
index d04a27adec8..2ee030ca83f 100644
--- a/source/blender/blenkernel/intern/constraint.c
+++ b/source/blender/blenkernel/intern/constraint.c
@@ -1463,12 +1463,10 @@ static void followpath_get_tarmat(struct Depsgraph *UNUSED(depsgraph),
      * currently for paths to work it needs to go through the bevlist/displist system (ton)
      */
 
-    if (ct->tar->runtime.curve_cache && ct->tar->runtime.curve_cache->path &&
-        ct->tar->runtime.curve_cache->path->data) {
+    if (ct->tar->runtime.curve_cache && ct->tar->runtime.curve_cache->anim_path_accum_length) {
       float quat[4];
       if ((data->followflag & FOLLOWPATH_STATIC) == 0) {
         /* animated position along curve depending on time */
-        Nurb *nu = cu->nurb.first;
         curvetime = cu->ctime - data->offset;
 
         /* ctime is now a proper var setting of Curve which gets set by Animato like any other var
@@ -1477,31 +1475,19 @@ static void followpath_get_tarmat(struct Depsgraph *UNUSED(depsgraph),
          * we divide the curvetime calculated in the previous step by the length of the path,
          * to get a time factor, which then gets clamped to lie within 0.0 - 1.0 range. */
         curvetime /= cu->pathlen;
-
-        if (nu && nu->flagu & CU_NURB_CYCLIC) {
-          /* If the curve is cyclic, enable looping around if the time is
-           * outside the bounds 0..1 */
-          if ((curvetime < 0.0f) || (curvetime > 1.0f)) {
-            curvetime -= floorf(curvetime);
-          }
-        }
-        else {
-          /* The curve is not cyclic, so clamp to the begin/end points. */
-          CLAMP(curvetime, 0.0f, 1.0f);
-        }
       }
       else {
         /* fixed position along curve */
         curvetime = data->offset_fac;
       }
 
-      if (where_on_path(ct->tar,
-                        curvetime,
-                        vec,
-                        dir,
-                        (data->followflag & FOLLOWPATH_FOLLOW) ? quat : NULL,
-                        &radius,
-                        NULL)) { /* quat_pt is quat or NULL*/
+      if (BKE_where_on_path(ct->tar,
+                            curvetime,
+                            vec,
+                            dir,
+                            (data->followflag & FOLLOWPATH_FOLLOW) ? quat : NULL,
+                            &radius,
+                            NULL)) { /* quat_pt is quat or NULL*/
         float totmat[4][4];
         unit_m4(totmat);
 
@@ -3784,8 +3770,7 @@ static void clampto_evaluate(bConstraint *con, bConstraintOb *cob, ListBase *tar
     BKE_object_minmax(ct->tar, curveMin, curveMax, true);
 
     /* get targetmatrix */
-    if (data->tar->runtime.curve_cache && data->tar->runtime.curve_cache->path &&
-        data->tar->runtime.curve_cache->path->data) {
+    if (data->tar->runtime.curve_cache && data->tar->runtime.curve_cache->anim_path_accum_length) {
       float vec[4], dir[3], totmat[4][4];
       float curvetime;
       short clamp_axis;
@@ -3869,7 +3854,7 @@ static void clampto_evaluate(bConstraint *con, bConstraintOb *cob, ListBase *tar
       }
 
       /* 3. position on curve */
-      if (where_on_path(ct->tar, curvetime, vec, dir, NULL, NULL, NULL)) {
+      if (BKE_where_on_path(ct->tar, curvetime, vec, dir, NULL, NULL, NULL)) {
         unit_m4(totmat);
         copy_v3_v3(totmat[3], vec);
 
diff --git a/source/blender/blenkernel/intern/curve_deform.c b/source/blender/blenkernel/intern/curve_deform.c
index 63da7c1dd11..10c6d2213ff 100644
--- a/source/blender/blenkernel/intern/curve_deform.c
+++ b/source/blender/blenkernel/intern/curve_deform.c
@@ -68,75 +68,7 @@ static void init_curve_deform(const Object *ob_curve, const Object *ob_target, C
 }
 
 /**
- * This makes sure we can extend for non-cyclic.
- *
- * \return Success.
- */
-static bool where_on_path_deform(const Object *ob_curve,
-                                 float ctime,
-                                 float r_vec[4],
-                                 float r_dir[3],
-                                 float r_quat[4],
-                                 float *r_radius)
-{
-  BevList *bl;
-  float ctime1;
-  int cycl = 0;
-
-  /* test for cyclic */
-  bl = ob_curve->runtime.curve_cache->bev.first;
-  if (!bl->nr) {
-    return false;
-  }
-  if (bl->poly > -1) {
-    cycl = 1;
-  }
-
-  if (cycl == 0) {
-    ctime1 = CLAMPIS(ctime, 0.0f, 1.0f);
-  }
-  else {
-    ctime1 = ctime;
-  }
-
-  /* vec needs 4 items */
-  if (where_on_path(ob_curve, ctime1, r_vec, r_dir, r_quat, r_radius, NULL)) {
-
-    if (cycl == 0) {
-      Path *path = ob_curve->runtime.curve_cache->path;
-      float dvec[3];
-
-      if (ctime < 0.0f) {
-        sub_v3_v3v3(dvec, path->data[1].vec, path->data[0].vec);
-        mul_v3_fl(dvec, ctime * (float)path->len);
-        add_v3_v3(r_vec, dvec);
-        if (r_quat) {
-          copy_qt_qt(r_quat, path->data[0].quat);
-        }
-        if (r_radius) {
-          *r_radius = path->data[0].radius;
-        }
-      }
-      else if (ctime > 1.0f) {
-        sub_v3_v3v3(dvec, path->data[path->len - 1].vec, path->data[path->len - 2].vec);
-        mul_v3_fl(dvec, (ctime - 1.0f) * (float)path->len);
-        add_v3_v3(r_vec, dvec);
-        if (r_quat) {
-          copy_qt_qt(r_quat, path->data[path->len - 1].quat);
-        }
-        if (r_radius) {
-          *r_radius = path->data[path->len - 1].radius;
-        }
-        /* weight - not used but could be added */
-      }
-    }
-    return true;
-  }
-  return false;
-}
-
-/**
- * For each point, rotate & translate to curve use path, since it has constant distances.
+ * For each point, rotate & translate to curve.
  *
  * \param co: local coord, result local too.
  * \param r_quat: returns quaternion for rotation,
@@ -155,7 +87,7 @@ static bool calc_curve_deform(
     return false;
   }
 
-  if (ob_curve->runtime.curve_cache->path == NULL) {
+  if (ob_curve->runtime.curve_cache->anim_path_accum_length == NULL) {
     return false; /* happens on append, cyclic dependencies and empty curves */
   }
 
@@ -172,8 +104,10 @@ static bool calc_curve_deform(
       }
     }
     else {
-      if (LIKELY(ob_curve->runtime.curve_cache->path->totdist > FLT_EPSILON)) {
-        fac = -(co[index] - cd->dmax[index]) / (ob_curve->runtime.curve_cache->path->totdist);
+      CurveCache *cc = ob_curve->runtime.curve_cache;
+      float totdist = BKE_anim_path_get_length(cc);
+      if (LIKELY(totdist > FLT_EPSILON)) {
+        fac = -(co[index] - cd->dmax[index]) / totdist;
       }
       else {
         fac = 0.0f;
@@ -192,8 +126,10 @@ static bool calc_curve_deform(
       }
     }
     else {
-      if (LIKELY(ob_curve->runtime.curve_cache->path->totdist > FLT_EPSILON)) {
-        fac = +(co[index] - cd->dmin[index]) / (ob_curve->runtime.curve_cache->path->totdist);
+      CurveCache *cc = ob_curve->runtime.curve_cache;
+      float totdist = BKE_anim_path_get_length(cc);
+      if (LIKELY(totdist > FLT_EPSILON)) {
+        fac = +(co[index] - cd->dmin[index]) / totdist;
       }
       else {
         fac = 0.0f;
@@ -201,7 +137,7 @@ static bool calc_curve_deform(
     }
   }
 
-  if (where_on_path_deform(ob_curve, fac, loc, dir, new_quat, &radius)) { /* returns OK */
+  if (BKE_where_on_path(ob_curve, fac, loc, dir, new_quat, &radius, NULL)) { /* returns OK */
     float quat[4], cent[3];
 
     if (cd->no_rot_axis) { /* set by caller */
diff --git a/source/blender/blenkernel/intern/displist.c b/source/blender/blenkernel/intern/displist.c
index 9022760fe34..2f6370fa5eb 100644
--- a/source/blender/blenkernel/intern/displist.c
+++ b/source/blender/blenkernel/intern/displist.c
@@ -1491,10 +1491,10 @@ static void do_makeDispListCurveTypes(Depsgraph *depsgraph,
      * was needed before and only not needed for orco calculation.
      */
     if (!for_orco) {
-      if (ob->runtime.curve_cache->path) {
-        free_path(ob->runtime.curve_cache->path);
+      if (ob->runtime.curve_cache->anim_path_accum_length) {
+        MEM_freeN(ob->runtime.curve_cache->anim_path_accum_length);
       }
-      ob->runtime.curve_cache->path = NULL;
+      ob->runtime.curve_cache->anim_path_accum_length = NULL;
     }
 
     if (ob->type == OB_FONT) {
@@ -1703,7 +1703,7 @@ static void do_makeDispListCurveTypes(Depsgraph *depsgraph,
     if (!for_orco) {
       if ((cu->flag & CU_PATH) ||
           DEG_get_eval_flags_for_id(depsgraph, &ob->id) & DAG_EVAL_NEED_CURVE_PATH) {
-        calc_curvepath(ob, &nubase);
+        BKE_anim_path_calc_data(ob);
       }
 
       BKE_nurbList_duplicate(&ob->runtime.curve_cache->deformed_nurbs, &nubase);
diff --git a/source/blender/blenkernel/intern/effect.c b/source/blender/blenkernel/intern/effect.c
index 4104b6080c5..e39749225ea 100644
--- a/source/blender/blenkernel/intern/effect.c
+++ b/source/blender/blenkernel/intern/effect.c
@@ -161,13 +161,13 @@ static void precalculate_effector(struct Depsgraph *depsgraph, EffectorCache *ef
   if (eff->pd->forcefield == PFIELD_GUIDE && eff->ob->type == OB_CURVE) {
     Curve *cu = eff->ob->data;
     if (cu->flag & CU_PATH) {
-      if (eff->ob->runtime.curve_cache == NULL || eff->ob->runtime.curve_cache->path == NULL ||
-          eff->ob->runtime.curve_cache->path->data == NULL) {
+      if (eff->ob->runtime.curve_cache == NULL ||
+          eff->ob->runtime.curve_cache->anim_path_accum_length == NULL) {
         BKE_displist_make_curveTypes(depsgraph, eff->scene, eff->ob, false, false);
       }
 
-      if (eff->ob->runtime.curve_cache->path && eff->ob->runtime.curve_cache->path->data) {
-        where_on_path(
+      if (eff->ob->runtime.curve_cache->anim_path_accum_length) {
+        BKE_where_on_path(
             eff->ob, 0.0, eff->guide_loc, eff->guide_dir, NULL, &eff->guide_radius, NULL);
         mul_m4_v3(eff->ob->obmat, eff->guide_loc);
         mul_mat3_m4_v3(eff->ob->obmat, eff->guide_dir);
diff --git a/source/blender/blenkernel/intern/font.c b/source/blender/blenkernel/intern/font.c
index 64f44240eed..92cc3c763b6 100644
--- a/source/blender/blenkernel/intern/font.c
+++ b/source/blender/blenkernel/intern/font.c
@@ -1275,7 +1275,7 @@ static bool vfont_to_curve(Object *ob,
   if (cu->textoncurve && cu->textoncurve->type == OB_CURVE) {
     BLI_assert(cu->textoncurve->runtime.curve_cache != NULL);
     if (cu->textoncurve->runtime.curve_cache != NULL &&
-        cu->textoncurve->runtime.curve_cache->path != NULL) {
+        cu->textoncurve->runtime.curve_cache->anim_path_accum_length != NULL) {
       float distfac, imat[4][4], imat3[3][3], cmat[3][3];
       float minx, maxx;
       float timeofs, sizefac;
@@ -1309,7 +1309,8 @@ static bool vfont_to_curve(Object *ob,
       /* length correction */
       const float chartrans_size_x = maxx - minx;
       if (chartrans_size_x != 0.0f) {
-        const float totdist = cu->textoncurve->runtime.curve_cache->path->totdist;
+        const CurveCache *cc = cu->textoncurve->runtime.curve_cache;
+        const float totdist = BKE_anim_path_get_length(cc);
         distfac = (sizefac * totdist) / chartrans_size_x;
         distfac = (distfac > 1.0f) ? (1.0f / distfac) : 1.0f;
       }
@@ -1363,8 +1364,8 @@ static bool vfont_to_curve(Object *ob,
 
         /* calc the right loc AND the right rot separately */
         /* vec, tvec need 4 items */
-        where_on_path(cu->textoncurve, ctime, vec, tvec, NULL, NULL, NULL);
-        where_on_path(cu->textoncurve, ctime + dtime, tvec, rotvec, NULL, NULL, NULL);
+        BKE_where_on_path(cu->textoncurve, ctime, vec, tvec, NULL, NULL, NULL);
+        BKE_where_on_path(cu->textoncurve, ctime + dtime, tvec, rotvec, NULL, NULL, NULL);
 
         mul_v3_fl(vec, sizefac);
 
diff --git a/source/blender/blenkernel/intern/object.c b/source/blender/blenkernel/intern/object.c
index 8c5a4966633..1c56312b38b 100644
--- a/source/blender/blenkernel/intern/object.c
+++ b/source/blender/blenkernel/intern/object.c
@@ -311,8 +311,8 @@ static void object_free_data(ID *id)
   /* Free runtime curves data. */
   if (ob->runtime.curve_cache) {
     BKE_curve_bevelList_free(&ob->runtime.curve_cache->bev);
-    if (ob->runtime.curve_cache->path) {
-      free_path(ob->runtime.curve_cache->path);
+    if (ob->runtime.curve_cache->anim_path_accum_length) {
+      MEM_freeN(ob->runtime.curve_cache->anim_path_accum_length);
     }
     MEM_freeN(ob->runtime.curve_cache);
     ob->runtime.curve_cache = NULL;
@@ -1188,8 +1188,8 @@ void BKE_object_free_curve_cache(Object *ob)
   if (ob->runtime.curve_cache) {
     BKE_displist_free(&ob->runtime.curve_cache->disp);
     BKE_curve_bevelList_free(&ob->runtime.curve_cache->bev);
-    if (ob->runtime.curve_cache->path) {
-      free_path(ob->runtime.curve_cache->path);
+    if (ob->runtime.curve_cache->anim_path_accum_length) {
+      MEM_freeN(ob->runtime.curve_cache->anim_path_accum_length);
     }
     BKE_nurbList_free(&ob->runtime.curve_cache->deformed_nurbs);
     MEM_freeN(ob->runtime.curve_cache);
@@ -3244,7 +3244,7 @@ static bool ob_parcurve(Object *ob, Object *par, float r_mat[4][4])
   if (par->runtime.curve_cache == NULL) {
     return false;
   }
-  if (par->runtime.curve_cache->path == NULL) {
+  if (par->runtime.curve_cache->anim_path_accum_length == NULL) {
     return false;
   }
 
@@ -3260,12 +3260,12 @@ static bool ob_parcurve(Object *ob, Object *par, float r_mat[4][4])
   else {
     ctime = cu->ctime;
   }
-  CLAMP(ctime, 0.0f, 1.0f);
 
   unit_m4(r_mat);
 
   /* vec: 4 items! */
-  if (where_on_path(par, ctime, vec, dir, (cu->flag & CU_FOLLOW) ? quat : NULL, &radius, NULL)) {
+  if (BKE_where_on_path(
+          par, ctime, vec, dir, (cu->flag & CU_FOLLOW) ? quat : NULL, &radius, NULL)) {
     if (cu->flag & CU_FOLLOW) {
       quat_apply_track(quat, ob->trackflag, ob->upflag);
       normalize_qt(quat);
diff --git a/source/blender/blenkernel/intern/particle.c b/source/blender/blenkernel/intern/particle.c
index e50b321900a..ae685357151 100644
--- a/source/blender/blenkernel/intern/particle.c
+++ b/source/blender/blenkernel/intern/particle.c
@@ -2417,14 +2417,15 @@ int do_guides(Depsgraph *depsgraph,
       cu = (Curve *)eff->ob->data;
 
       if (pd->flag & PFIELD_GUIDE_PATH_ADD) {
-        if (where_on_path(
+        if (BKE_where_on_path(
                 eff->ob, data->strength * guidetime, guidevec, guidedir, NULL, &radius, &weight) ==
             0) {
           return 0;
         }
       }
       else {
-        if (where_on_path(eff->ob, guidetime, guidevec, guidedir, NULL, &radius, &weight) == 0) {
+        if (BKE_where_on_path(eff->ob, guidetime, guidevec, guidedir, NULL, &radius, &weight) ==
+            0) {
           return 0;
         }
       }
diff --git a/source/blender/draw/engines/overlay/overlay_extra.c b/source/blender/draw/engines/overlay/overlay_extra.c
index 00429a19cf4..2e1c0165513 100644
--- a/source/blender/draw/engines/overlay/overlay_extra.c
+++ b/source/blender/draw/engines/overlay/overlay_extra.c
@@ -542,16 +542,15 @@ static void OVERLAY_forcefield(OVERLAY_ExtraCallBuffers *cb, Object *ob, ViewLay
       DRW_buffer_add_entry(cb->field_vortex, color, &instdata);
       break;
     case PFIELD_GUIDE:
-      if (cu && (cu->flag & CU_PATH) && ob->runtime.curve_cache->path &&
-          ob->runtime.curve_cache->path->data) {
+      if (cu && (cu->flag & CU_PATH) && ob->runtime.curve_cache->anim_path_accum_length) {
         instdata.size_x = instdata.size_y = instdata.size_z = pd->f_strength;
         float pos[4], tmp[3];
-        where_on_path(ob, 0.0f, pos, tmp, NULL, NULL, NULL);
+        BKE_where_on_path(ob, 0.0f, pos, tmp, NULL, NULL, NULL);
         copy_v3_v3(instdata.pos, ob->obmat[3]);
         translate_m4(instdata.mat, pos[0], pos[1], pos[2]);
         DRW_buffer_add_entry(cb->field_curve, color, &instdata);
 
-        where_on_path(ob, 1.0f, pos, tmp, NULL, NULL, NULL);
+        BKE_where_on_path(ob, 1.0f, pos, tmp, NULL, NULL, NULL);
         copy_v3_v3(instdata.pos, ob->obmat[3]);
         translate_m4(instdata.mat, pos[0], pos[1], pos[2]);
         DRW_buffer_add_entry(cb->field_sphere_limit, color, &instdata);
diff --git a/source/blender/editors/object/object_relations.c b/source/blender/editors/object/object_relations.c
index 0aa739c2fc8..a7308002e76 100644
--- a/source/blender/editors/object/object_relations.c
+++ b/source/blender/editors/object/object_relations.c
@@ -812,7 +812,8 @@ bool ED_object_parent_set(ReportList *reports,
               if (md) {
                 ((CurveModifierData *)md)->object = par;
               }
-              if (par->runtime.curve_cache && par->runtime.curve_cache->path == NULL) {
+              if (par->runtime.curve_cache &&
+                  par->runtime.curve_cache->anim_path_accum_length == NULL) {
                 DEG_id_tag_update(&par->id, ID_RECALC_GEOMETRY);
               }
             }
diff --git a/source/blender/makesdna/DNA_curve_types.h b/source/blender/makesdna/DNA_curve_types.h
index 02a1a713d02..517c5c6c5f1 100644
--- a/source/blender/makesdna/DNA_curve_types.h
+++ b/source/blender/makesdna/DNA_curve_types.h
@@ -47,25 +47,6 @@ struct VFont;
 /* These two Lines with # tell makesdna this struct can be excluded. */
 #
 #
-typedef struct PathPoint {
-  /** Grr, cant get rid of tilt yet. */
-  float vec[4];
-  float quat[4];
-  float radius, weight;
-} PathPoint;
-
-/* These two Lines with # tell makesdna this struct can be excluded. */
-#
-#
-typedef struct Path {
-  struct PathPoint *data;
-  int len;
-  float totdist;
-} Path;
-
-/* These two Lines with # tell makesdna this struct can be excluded. */
-#
-#
 typedef struct BevPoint {
   float vec[3], tilt, radius, weight, offset;
   /** 2D Only. */
diff --git a/source/blender/makesrna/intern/rna_constraint.c b/source/blender/makesrna/intern/rna_constraint.c
index 843cb326be2..a3934b12a44 100644
--- a/source/blender/makesrna/intern/rna_constraint.c
+++ b/source/blender/makesrna/intern/rna_constraint.c
@@ -1923,7 +1923,8 @@ static void rna_def_constraint_follow_path(BlenderRNA *brna)
 
   prop = RNA_def_property(srna, "offset_factor", PROP_FLOAT, PROP_FACTOR);
   RNA_def_property_float_sdna(prop, NULL, "offset_fac");
-  RNA_def_property_range(prop, 0.0f, 1.0f);
+  RNA_def_property_range(prop, -FLT_MAX, FLT_MAX);
+  RNA_def_property_ui_range(prop, 0.0f, 1.0f, 0.01, 3);
   RNA_def_property_ui_text(
       prop, "Offset Factor", "Percentage value defining target position along length of curve");
   RNA_def_property_update(prop, NC_OBJECT | ND_CONSTRAINT, "rna_Constraint_update");
diff --git a/source/blender/modifiers/intern/MOD_array.c b/source/blender/modifiers/intern/MOD_array.c
index b48bf722526..0282f0d2934 100644
--- a/source/blender/modifiers/intern/MOD_array.c
+++ b/source/blender/modifiers/intern/MOD_array.c
@@ -39,6 +39,7 @@
 #include "DNA_scene_types.h"
 #include "DNA_screen_types.h"
 
+#include "BKE_anim_path.h"
 #include "BKE_context.h"
 #include "BKE_curve.h"
 #include "BKE_displist.h"
@@ -471,9 +472,9 @@ static Mesh *arrayModifier_doArray(ArrayModifierData *amd,
   if (amd->fit_type == MOD_ARR_FITCURVE && amd->curve_ob != NULL) {
     Object *curve_ob = amd->curve_ob;
     CurveCache *curve_cache = curve_ob->runtime.curve_cache;
-    if (curve_cache != NULL && curve_cache->path != NULL) {
+    if (curve_cache != NULL && curve_cache->anim_path_accum_length != NULL) {
       float scale_fac = mat4_to_scale(curve_ob->obmat);
-      length = scale_fac * curve_cache->path->totdist;
+      length = scale_fac * BKE_anim_path_get_length(curve_cache);
     }
   }