Geometry Noes: Curve Resample Node

This node generates a naturally parametarized (even length edge) poly
spline version of every spline in the input. There are two modes,
"Count", and "Length". These are similar to the same options for the
line primitive node in end points mode.

I implemented this instead of a "Sample Points" node, because for this
operation it's trivial to keep the result as a curve, which is nice
since it increases flexibility, and because it can make instancing
simpler, i.e. using the transforms of each evaluated point rather than
requiring the construction of a "rotation" attribute.

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

1 files changed, 67 insertions, 2 deletions

diff --git a/source/blender/blenkernel/intern/spline_base.cc b/source/blender/blenkernel/intern/spline_base.cc
index 31c2178fa3f..e2b1118a0b2 100644
--- a/source/blender/blenkernel/intern/spline_base.cc
+++ b/source/blender/blenkernel/intern/spline_base.cc
@@ -16,11 +16,13 @@
 
 #include "BLI_array.hh"
 #include "BLI_span.hh"
-
-#include "FN_generic_virtual_array.hh"
+#include "BLI_timeit.hh"
 
 #include "BKE_spline.hh"
 
+#include "FN_generic_virtual_array.hh"
+
+using blender::Array;
 using blender::float3;
 using blender::IndexRange;
 using blender::MutableSpan;
@@ -265,6 +267,69 @@ Spline::LookupResult Spline::lookup_evaluated_length(const float length) const
   return LookupResult{index, next_index, factor};
 }
 
+/**
+ * Return an array of evenly spaced samples along the length of the spline. The samples are indices
+ * and factors to the next index encoded in floats. The logic for converting from the float values
+ * to interpolation data is in #lookup_data_from_index_factor.
+ */
+Array<float> Spline::sample_uniform_index_factors(const int samples_size) const
+{
+  const Span<float> lengths = this->evaluated_lengths();
+
+  BLI_assert(samples_size > 0);
+  Array<float> samples(samples_size);
+
+  samples[0] = 0.0f;
+  if (samples_size == 1) {
+    return samples;
+  }
+
+  const float total_length = this->length();
+  const float sample_length = total_length / (samples_size - 1);
+
+  /* Store the length at the previous evaluated 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;
+  int i_sample = 1;
+  for (const int i_evaluated : IndexRange(this->evaluated_edges_size())) {
+    const float length = lengths[i_evaluated];
+
+    /* Add every sample that fits in this evaluated edge. */
+    while ((sample_length * i_sample) < length && i_sample < samples_size) {
+      const float factor = (sample_length * i_sample - prev_length) / (length - prev_length);
+      samples[i_sample] = i_evaluated + factor;
+      i_sample++;
+    }
+
+    prev_length = length;
+  }
+
+  samples.last() = lengths.size();
+
+  return samples;
+}
+
+Spline::LookupResult Spline::lookup_data_from_index_factor(const float index_factor) const
+{
+  const int points_len = this->evaluated_points_size();
+
+  if (is_cyclic_) {
+    if (index_factor < points_len) {
+      const int index = std::floor(index_factor);
+      const int next_index = (index < points_len - 1) ? index + 1 : 0;
+      return LookupResult{index, next_index, index_factor - index};
+    }
+    return LookupResult{points_len - 1, 0, 1.0f};
+  }
+
+  if (index_factor < points_len - 1) {
+    const int index = std::floor(index_factor);
+    const int next_index = index + 1;
+    return LookupResult{index, next_index, index_factor - index};
+  }
+  return LookupResult{points_len - 2, points_len - 1, 1.0f};
+}
+
 void Spline::bounds_min_max(float3 &min, float3 &max, const bool use_evaluated) const
 {
   Span<float3> positions = use_evaluated ? this->evaluated_positions() : this->positions();