Add a utility for sampling segment indices and factors from arbitrary

lengths along a set of points. This can be used for the sample curves
node, or finding new points along a curve when extending
or shrinking it.

This commit uses it in the snake hook brush as an example.

The logic is similar to the uniform length sampling, but the next
sample length is retrieved from the input instead of multiplication.

For the sample node in the future, though this sort of sampling can be
potentially done more efficiently for specific curve types besides
poly curves, it's simpler, at least as a start, to work on a set of
evaluated points that can be treated like a poly curve.

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

4 files changed, 166 insertions, 34 deletions

diff --git a/source/blender/blenlib/BLI_length_parameterize.hh b/source/blender/blenlib/BLI_length_parameterize.hh
index e4a4e9cbb9c..6fe1c6513a2 100644
--- a/source/blender/blenlib/BLI_length_parameterize.hh
+++ b/source/blender/blenlib/BLI_length_parameterize.hh
@@ -77,4 +77,22 @@ void create_uniform_samples(Span<float> lengths,
                             MutableSpan<int> indices,
                             MutableSpan<float> factors);
 
+/**
+ * For each provided sample length, find the segment index and interpolation factor.
+ *
+ * \param lengths: The accumulated lengths of the original elements being sampled.
+ * Could be calculated by #accumulate_lengths.
+ * \param sample_lengths: Sampled locations in the #lengths array. Must be sorted and is expected
+ * to be within the range of the #lengths values.
+ * \param cyclic: Whether the points described by the #lenghts input is cyclic. This is likely
+ * redundant information theoretically.
+ * \param indices: The index of the previous point at each sample.
+ * \param factors: The portion of the length in each segment at each sample.
+ */
+void create_samples_from_sorted_lengths(Span<float> lengths,
+                                        Span<float> sample_lengths,
+                                        bool cyclic,
+                                        MutableSpan<int> indices,
+                                        MutableSpan<float> factors);
+
 }  // namespace blender::length_parameterize
diff --git a/source/blender/blenlib/intern/length_parameterize.cc b/source/blender/blenlib/intern/length_parameterize.cc
index d6862b96944..7c0fc860b53 100644
--- a/source/blender/blenlib/intern/length_parameterize.cc
+++ b/source/blender/blenlib/intern/length_parameterize.cc
@@ -77,4 +77,68 @@ void create_uniform_samples(const Span<float> lengths,
   }
 }
 
+void create_samples_from_sorted_lengths(const Span<float> lengths,
+                                        const Span<float> sample_lengths,
+                                        const bool cyclic,
+                                        MutableSpan<int> indices,
+                                        MutableSpan<float> factors)
+{
+  BLI_assert(std::is_sorted(lengths.begin(), lengths.end()));
+  BLI_assert(std::is_sorted(sample_lengths.begin(), sample_lengths.end()));
+  BLI_assert(indices.size() == sample_lengths.size());
+  BLI_assert(indices.size() == factors.size());
+  const int segments_num = lengths.size();
+  const int points_num = cyclic ? segments_num : segments_num + 1;
+
+  const float total_length = lengths.last();
+  if (total_length == 0.0f) {
+    indices.fill(0);
+    factors.fill(0.0f);
+    return;
+  }
+
+  int i_dst = 0;
+  /* Store the length at the previous point in a variable so it can start out at zero
+   * (the lengths array doesn't contain 0 for the first point). */
+  float prev_length = 0.0f;
+  for (const int i_src : IndexRange(points_num - 1)) {
+    const float next_length = lengths[i_src];
+    const float segment_length = next_length - prev_length;
+    if (segment_length == 0.0f) {
+      continue;
+    }
+    /* Add every sample that fits in this segment. It's also necessary to check if the last sample
+     * has been reached, since there is no upper bound on the number of samples in each segment. */
+    const float segment_length_inv = 1.0f / segment_length;
+    while (i_dst < sample_lengths.size() && sample_lengths[i_dst] < next_length) {
+      const float length_in_segment = sample_lengths[i_dst] - prev_length;
+      const float factor = length_in_segment * segment_length_inv;
+      indices[i_dst] = i_src;
+      factors[i_dst] = factor;
+      i_dst++;
+    }
+
+    prev_length = next_length;
+  }
+
+  /* Add the samples on the last cyclic segment if necessary, and also the samples
+   * that weren't created in the previous loop due to floating point inaccuracy. */
+  if (cyclic && lengths.size() > 1) {
+    const float segment_length = lengths.last() - lengths.last(1);
+    while (sample_lengths[i_dst] < total_length) {
+      const float length_in_segment = sample_lengths[i_dst] - prev_length;
+      const float factor = length_in_segment / segment_length;
+      indices[i_dst] = points_num - 1;
+      factors[i_dst] = factor;
+      i_dst++;
+    }
+    indices.drop_front(i_dst).fill(points_num - 1);
+    factors.drop_front(i_dst).fill(1.0f);
+  }
+  else {
+    indices.drop_front(i_dst).fill(points_num - 2);
+    factors.drop_front(i_dst).fill(1.0f);
+  }
+}
+
 }  // namespace blender::length_parameterize
diff --git a/source/blender/blenlib/tests/BLI_length_parameterize_test.cc b/source/blender/blenlib/tests/BLI_length_parameterize_test.cc
index 4a8b7095888..b63e3a0ec86 100644
--- a/source/blender/blenlib/tests/BLI_length_parameterize_test.cc
+++ b/source/blender/blenlib/tests/BLI_length_parameterize_test.cc
@@ -199,4 +199,60 @@ TEST(length_parameterize, InterpolateColor)
   }
 }
 
+TEST(length_parameterize, ArbitraryFloatSimple)
+{
+  Array<float> values{{0, 1, 4}};
+  Array<float> lengths = calculate_lengths(values.as_span(), false);
+
+  Array<float> sample_lengths{{0.5f, 1.5f, 2.0f, 4.0f}};
+  Array<int> indices(4);
+  Array<float> factors(4);
+  create_samples_from_sorted_lengths(lengths, sample_lengths, false, indices, factors);
+  Array<float> results(4);
+  linear_interpolation<float>(values, indices, factors, results);
+  results.as_span().print_as_lines("results");
+  Array<float> expected({
+      0.5f,
+      1.5f,
+      2.0f,
+      4.0f,
+  });
+  for (const int i : results.index_range()) {
+    EXPECT_NEAR(results[i], expected[i], 1e-5);
+  }
+}
+
+TEST(length_parameterize, ArbitraryFloat2)
+{
+  Array<float2> values{{{0, 0}, {1, 0}, {1, 1}, {0, 1}}};
+  Array<float> lengths = calculate_lengths(values.as_span(), true);
+
+  Array<float> sample_lengths{
+      {0.5f, 1.5f, 2.0f, 2.0f, 2.1f, 2.5f, 3.5f, 3.6f, 3.8f, 3.85f, 3.90f, 4.0f}};
+  Array<int> indices(12);
+  Array<float> factors(12);
+  create_samples_from_sorted_lengths(lengths, sample_lengths, true, indices, factors);
+  Array<float2> results(12);
+  linear_interpolation<float2>(values, indices, factors, results);
+  results.as_span().print_as_lines("results");
+  Array<float2> expected({
+      {0.5f, 0.0f},
+      {1.0f, 0.5f},
+      {1.0f, 1.0f},
+      {1.0f, 1.0f},
+      {0.9f, 1.0f},
+      {0.5f, 1.0f},
+      {0.0f, 0.5f},
+      {0.0f, 0.4f},
+      {0.0f, 0.2f},
+      {0.0f, 0.15f},
+      {0.0f, 0.1f},
+      {0.0f, 0.0f},
+  });
+  for (const int i : results.index_range()) {
+    EXPECT_NEAR(results[i].x, expected[i].x, 1e-5);
+    EXPECT_NEAR(results[i].y, expected[i].y, 1e-5);
+  }
+}
+
 }  // namespace blender::length_parameterize::tests
diff --git a/source/blender/editors/sculpt_paint/curves_sculpt_snake_hook.cc b/source/blender/editors/sculpt_paint/curves_sculpt_snake_hook.cc
index 39321243553..b367c5bb6ec 100644
--- a/source/blender/editors/sculpt_paint/curves_sculpt_snake_hook.cc
+++ b/source/blender/editors/sculpt_paint/curves_sculpt_snake_hook.cc
@@ -7,6 +7,7 @@
 #include "BLI_float4x4.hh"
 #include "BLI_index_mask_ops.hh"
 #include "BLI_kdtree.h"
+#include "BLI_length_parameterize.hh"
 #include "BLI_rand.hh"
 #include "BLI_vector.hh"
 
@@ -232,43 +233,36 @@ struct SnakeHookOperatorExecutor {
     });
   }
 
-  void move_last_point_and_resample(MutableSpan<float3> positions_cu,
-                                    const float3 &new_last_point_position_cu) const
+  void move_last_point_and_resample(MutableSpan<float3> positions,
+                                    const float3 &new_last_position) const
   {
-    Vector<float> old_lengths_cu;
-    old_lengths_cu.append(0.0f);
-    /* Used to (1) normalize the segment sizes over time and (2) support making zero-length
-     * segments */
-    const float extra_length = 0.001f;
-    for (const int segment_i : IndexRange(positions_cu.size() - 1)) {
-      const float3 &p1_cu = positions_cu[segment_i];
-      const float3 &p2_cu = positions_cu[segment_i + 1];
-      const float length_cu = math::distance(p1_cu, p2_cu);
-      old_lengths_cu.append(old_lengths_cu.last() + length_cu + extra_length);
-    }
-    Vector<float> point_factors;
-    for (float &old_length_cu : old_lengths_cu) {
-      point_factors.append(old_length_cu / old_lengths_cu.last());
+    /* Find the accumulated length of each point in the original curve,
+     * treating it as a poly curve for performance reasons and simplicity. */
+    Array<float> orig_lengths(length_parameterize::lengths_num(positions.size(), false));
+    length_parameterize::accumulate_lengths<float3>(positions, false, orig_lengths);
+    const float orig_total_length = orig_lengths.last();
+
+    /* Find the factor by which the new curve is shorter or longer than the original. */
+    const float new_last_segment_length = math::distance(positions.last(1), new_last_position);
+    const float new_total_length = orig_lengths.last(1) + new_last_segment_length;
+    const float length_factor = new_total_length / orig_total_length;
+
+    /* Calculate the lengths to sample the original curve with by scaling the original lengths. */
+    Array<float> new_lengths(positions.size() - 1);
+    new_lengths.first() = 0.0f;
+    for (const int i : new_lengths.index_range().drop_front(1)) {
+      new_lengths[i] = orig_lengths[i - 1] * length_factor;
     }
 
-    PolySpline new_spline;
-    new_spline.resize(positions_cu.size());
-    MutableSpan<float3> new_spline_positions_cu = new_spline.positions();
-    for (const int i : IndexRange(positions_cu.size() - 1)) {
-      new_spline_positions_cu[i] = positions_cu[i];
-    }
-    new_spline_positions_cu.last() = new_last_point_position_cu;
-    new_spline.mark_cache_invalid();
-
-    for (const int i : positions_cu.index_range()) {
-      const float factor = point_factors[i];
-      const Spline::LookupResult lookup = new_spline.lookup_evaluated_factor(factor);
-      const float index_factor = lookup.evaluated_index + lookup.factor;
-      float3 p_cu;
-      new_spline.sample_with_index_factors<float3>(
-          new_spline_positions_cu, {&index_factor, 1}, {&p_cu, 1});
-      positions_cu[i] = p_cu;
-    }
+    Array<int> indices(positions.size() - 1);
+    Array<float> factors(positions.size() - 1);
+    length_parameterize::create_samples_from_sorted_lengths(
+        orig_lengths, new_lengths, false, indices, factors);
+
+    Array<float3> new_positions(positions.size() - 1);
+    length_parameterize::linear_interpolation<float3>(positions, indices, factors, new_positions);
+    positions.drop_back(1).copy_from(new_positions);
+    positions.last() = new_last_position;
   }
 };