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

7 files changed, 105 insertions, 2 deletions

diff --git a/source/blender/blenkernel/BKE_node.h b/source/blender/blenkernel/BKE_node.h
index 7978a0114ef..93742999498 100644
--- a/source/blender/blenkernel/BKE_node.h
+++ b/source/blender/blenkernel/BKE_node.h
@@ -1420,6 +1420,7 @@ int ntreeTexExecTree(struct bNodeTree *ntree,
 #define GEO_NODE_ATTRIBUTE_TRANSFER 1044
 #define GEO_NODE_CURVE_TO_MESH 1045
 #define GEO_NODE_ATTRIBUTE_CURVE_MAP 1046
+#define GEO_NODE_CURVE_RESAMPLE 1047
 
 /** \} */
 
diff --git a/source/blender/blenkernel/BKE_spline.hh b/source/blender/blenkernel/BKE_spline.hh
index 098abf6de65..fda603d57bf 100644
--- a/source/blender/blenkernel/BKE_spline.hh
+++ b/source/blender/blenkernel/BKE_spline.hh
@@ -113,6 +113,7 @@ class Spline {
   bool is_cyclic() const;
   void set_cyclic(const bool value);
 
+  virtual void resize(const int size) = 0;
   virtual blender::MutableSpan<blender::float3> positions() = 0;
   virtual blender::Span<blender::float3> positions() const = 0;
   virtual blender::MutableSpan<float> radii() = 0;
@@ -163,6 +164,9 @@ class Spline {
   LookupResult lookup_evaluated_factor(const float factor) const;
   LookupResult lookup_evaluated_length(const float length) const;
 
+  blender::Array<float> sample_uniform_index_factors(const int samples_size) const;
+  LookupResult lookup_data_from_index_factor(const float index_factor) const;
+
   /**
    * Interpolate a virtual array of data with the size of the number of control points to the
    * evaluated points. For poly splines, the lifetime of the returned virtual array must not
@@ -248,6 +252,7 @@ class BezierSpline final : public Spline {
                  const float radius,
                  const float tilt);
 
+  void resize(const int size) final;
   blender::MutableSpan<blender::float3> positions() final;
   blender::Span<blender::float3> positions() const final;
   blender::MutableSpan<float> radii() final;
@@ -387,6 +392,7 @@ class NURBSpline final : public Spline {
   bool check_valid_size_and_order() const;
   int knots_size() const;
 
+  void resize(const int size) final;
   blender::MutableSpan<blender::float3> positions() final;
   blender::Span<blender::float3> positions() const final;
   blender::MutableSpan<float> radii() final;
@@ -441,6 +447,7 @@ class PolySpline final : public Spline {
 
   void add_point(const blender::float3 position, const float radius, const float tilt);
 
+  void resize(const int size) final;
   blender::MutableSpan<blender::float3> positions() final;
   blender::Span<blender::float3> positions() const final;
   blender::MutableSpan<float> radii() final;
diff --git a/source/blender/blenkernel/intern/node.cc b/source/blender/blenkernel/intern/node.cc
index 05eb7e43441..b5969970157 100644
--- a/source/blender/blenkernel/intern/node.cc
+++ b/source/blender/blenkernel/intern/node.cc
@@ -4967,6 +4967,7 @@ static void registerGeometryNodes()
   register_node_type_geo_bounding_box();
   register_node_type_geo_collection_info();
   register_node_type_geo_curve_to_mesh();
+  register_node_type_geo_curve_resample();
   register_node_type_geo_edge_split();
   register_node_type_geo_is_viewport();
   register_node_type_geo_join_geometry();
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();
diff --git a/source/blender/blenkernel/intern/spline_bezier.cc b/source/blender/blenkernel/intern/spline_bezier.cc
index f62718011da..4d4e1b386c4 100644
--- a/source/blender/blenkernel/intern/spline_bezier.cc
+++ b/source/blender/blenkernel/intern/spline_bezier.cc
@@ -73,6 +73,18 @@ void BezierSpline::add_point(const float3 position,
   this->mark_cache_invalid();
 }
 
+void BezierSpline::resize(const int size)
+{
+  handle_types_left_.resize(size);
+  handle_positions_left_.resize(size);
+  positions_.resize(size);
+  handle_types_right_.resize(size);
+  handle_positions_right_.resize(size);
+  radii_.resize(size);
+  tilts_.resize(size);
+  this->mark_cache_invalid();
+}
+
 MutableSpan<float3> BezierSpline::positions()
 {
   return positions_;
diff --git a/source/blender/blenkernel/intern/spline_nurbs.cc b/source/blender/blenkernel/intern/spline_nurbs.cc
index 37d1232cfeb..2022b9fb85a 100644
--- a/source/blender/blenkernel/intern/spline_nurbs.cc
+++ b/source/blender/blenkernel/intern/spline_nurbs.cc
@@ -78,6 +78,15 @@ void NURBSpline::add_point(const float3 position,
   this->mark_cache_invalid();
 }
 
+void NURBSpline::resize(const int size)
+{
+  positions_.resize(size);
+  radii_.resize(size);
+  tilts_.resize(size);
+  weights_.resize(size);
+  this->mark_cache_invalid();
+}
+
 MutableSpan<float3> NURBSpline::positions()
 {
   return positions_;
diff --git a/source/blender/blenkernel/intern/spline_poly.cc b/source/blender/blenkernel/intern/spline_poly.cc
index 09c578c0503..ab6f4704a88 100644
--- a/source/blender/blenkernel/intern/spline_poly.cc
+++ b/source/blender/blenkernel/intern/spline_poly.cc
@@ -44,6 +44,14 @@ void PolySpline::add_point(const float3 position, const float radius, const floa
   this->mark_cache_invalid();
 }
 
+void PolySpline::resize(const int size)
+{
+  positions_.resize(size);
+  radii_.resize(size);
+  tilts_.resize(size);
+  this->mark_cache_invalid();
+}
+
 MutableSpan<float3> PolySpline::positions()
 {
   return positions_;