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

release/scripts/startup/nodeitems_builtins.py

@@ -508,6 +508,7 @@ geometry_node_categories = [
     ]),
     GeometryNodeCategory("GEO_CURVE", "Curve", items=[
         NodeItem("GeometryNodeCurveToMesh"),
+        NodeItem("GeometryNodeCurveResample"),
     ]),
     GeometryNodeCategory("GEO_GEOMETRY", "Geometry", items=[
         NodeItem("GeometryNodeBoundBox"),

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
 
 /** \} */
 

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;

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();

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();

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_;

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_;

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_;

source/blender/makesdna/DNA_node_types.h

@@ -1320,6 +1320,11 @@ typedef struct NodeSwitch {
   uint8_t input_type;
 } NodeSwitch;
 
+typedef struct NodeGeometryCurveResample {
+  /* GeometryNodeCurveSampleMode. */
+  uint8_t mode;
+} NodeGeometryCurveResample;
+
 typedef struct NodeGeometryAttributeTransfer {
   /* AttributeDomain. */
   int8_t domain;
@@ -1821,6 +1826,11 @@ typedef enum GeometryNodeMeshLineCountMode {
   GEO_NODE_MESH_LINE_COUNT_RESOLUTION = 1,
 } GeometryNodeMeshLineCountMode;
 
+typedef enum GeometryNodeCurveSampleMode {
+  GEO_NODE_CURVE_SAMPLE_COUNT = 0,
+  GEO_NODE_CURVE_SAMPLE_LENGTH = 1,
+} GeometryNodeCurveSampleMode;
+
 typedef enum GeometryNodeAttributeTransferMapMode {
   GEO_NODE_ATTRIBUTE_TRANSFER_NEAREST_FACE_INTERPOLATED = 0,
   GEO_NODE_ATTRIBUTE_TRANSFER_NEAREST = 1,

source/blender/makesrna/intern/rna_nodetree.c

@@ -9744,6 +9744,33 @@ static void def_geo_switch(StructRNA *srna)
   RNA_def_property_update(prop, NC_NODE | NA_EDITED, "rna_Node_socket_update");
 }
 
+static void def_geo_curve_resample(StructRNA *srna)
+{
+  PropertyRNA *prop;
+
+  static EnumPropertyItem mode_items[] = {
+      {GEO_NODE_CURVE_SAMPLE_COUNT,
+       "COUNT",
+       0,
+       "Count",
+       "Sample the specified number of points along each spline"},
+      {GEO_NODE_CURVE_SAMPLE_LENGTH,
+       "LENGTH",
+       0,
+       "Length",
+       "Calculate the number of samples by splitting each spline into segments with the specified "
+       "length"},
+      {0, NULL, 0, NULL, NULL},
+  };
+
+  RNA_def_struct_sdna_from(srna, "NodeGeometryCurveResample", "storage");
+
+  prop = RNA_def_property(srna, "mode", PROP_ENUM, PROP_NONE);
+  RNA_def_property_enum_items(prop, mode_items);
+  RNA_def_property_ui_text(prop, "Mode", "How to specify the amount of samples");
+  RNA_def_property_update(prop, NC_NODE | NA_EDITED, "rna_Node_socket_update");
+}
+
 static void def_geo_attribute_transfer(StructRNA *srna)
 {
   static EnumPropertyItem mapping_items[] = {

source/blender/nodes/CMakeLists.txt

@@ -162,6 +162,7 @@ set(SRC
   geometry/nodes/node_geo_collection_info.cc
   geometry/nodes/node_geo_common.cc
   geometry/nodes/node_geo_curve_to_mesh.cc
+  geometry/nodes/node_geo_curve_resample.cc
   geometry/nodes/node_geo_edge_split.cc
   geometry/nodes/node_geo_is_viewport.cc
   geometry/nodes/node_geo_join_geometry.cc

source/blender/nodes/NOD_geometry.h

@@ -50,6 +50,7 @@ void register_node_type_geo_boolean(void);
 void register_node_type_geo_bounding_box(void);
 void register_node_type_geo_collection_info(void);
 void register_node_type_geo_curve_to_mesh(void);
+void register_node_type_geo_curve_resample(void);
 void register_node_type_geo_edge_split(void);
 void register_node_type_geo_is_viewport(void);
 void register_node_type_geo_join_geometry(void);

source/blender/nodes/NOD_static_types.h

@@ -314,6 +314,7 @@ DefNode(GeometryNode, GEO_NODE_SWITCH, def_geo_switch, "SWITCH", Switch, "Switch
 DefNode(GeometryNode, GEO_NODE_ATTRIBUTE_TRANSFER, def_geo_attribute_transfer, "ATTRIBUTE_TRANSFER", AttributeTransfer, "Attribute Transfer", "")
 DefNode(GeometryNode, GEO_NODE_CURVE_TO_MESH, 0, "CURVE_TO_MESH", CurveToMesh, "Curve to Mesh", "")
 DefNode(GeometryNode, GEO_NODE_ATTRIBUTE_CURVE_MAP, def_geo_attribute_curve_map, "ATTRIBUTE_CURVE_MAP", AttributeCurveMap, "Attribute Curve Map", "")
+DefNode(GeometryNode, GEO_NODE_CURVE_RESAMPLE, def_geo_curve_resample, "CURVE_RESAMPLE", CurveResample, "Resample Curve", "")
 
 /* undefine macros */
 #undef DefNode

source/blender/nodes/geometry/nodes/node_geo_curve_resample.cc

@@ -0,0 +1,201 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#include "BLI_array.hh"
+#include "BLI_task.hh"
+#include "BLI_timeit.hh"
+
+#include "BKE_attribute_math.hh"
+#include "BKE_spline.hh"
+
+#include "UI_interface.h"
+#include "UI_resources.h"
+
+#include "node_geometry_util.hh"
+
+using blender::fn::GVArray_For_Span;
+using blender::fn::GVArray_Typed;
+
+static bNodeSocketTemplate geo_node_curve_resample_in[] = {
+    {SOCK_GEOMETRY, N_("Geometry")},
+    {SOCK_INT, N_("Count"), 10, 0, 0, 0, 1, 100000},
+    {SOCK_FLOAT, N_("Length"), 0.1f, 0.0f, 0.0f, 0.0f, 0.001f, FLT_MAX, PROP_DISTANCE},
+    {-1, ""},
+};
+
+static bNodeSocketTemplate geo_node_curve_resample_out[] = {
+    {SOCK_GEOMETRY, N_("Geometry")},
+    {-1, ""},
+};
+
+static void geo_node_curve_resample_layout(uiLayout *layout, bContext *UNUSED(C), PointerRNA *ptr)
+{
+  uiItemR(layout, ptr, "mode", UI_ITEM_R_EXPAND, nullptr, ICON_NONE);
+}
+
+static void geo_node_curve_resample_init(bNodeTree *UNUSED(tree), bNode *node)
+{
+  NodeGeometryCurveResample *data = (NodeGeometryCurveResample *)MEM_callocN(
+      sizeof(NodeGeometryCurveResample), __func__);
+
+  data->mode = GEO_NODE_CURVE_SAMPLE_COUNT;
+  node->storage = data;
+}
+
+static void geo_node_curve_resample_update(bNodeTree *UNUSED(ntree), bNode *node)
+{
+  NodeGeometryCurveResample &node_storage = *(NodeGeometryCurveResample *)node->storage;
+  const GeometryNodeCurveSampleMode mode = (GeometryNodeCurveSampleMode)node_storage.mode;
+
+  bNodeSocket *count_socket = ((bNodeSocket *)node->inputs.first)->next;
+  bNodeSocket *length_socket = count_socket->next;
+
+  nodeSetSocketAvailability(count_socket, mode == GEO_NODE_CURVE_SAMPLE_COUNT);
+  nodeSetSocketAvailability(length_socket, mode == GEO_NODE_CURVE_SAMPLE_LENGTH);
+}
+
+namespace blender::nodes {
+
+struct SampleModeParam {
+  GeometryNodeCurveSampleMode mode;
+  std::optional<float> length;
+  std::optional<int> count;
+};
+
+template<typename T>
+static void sample_span_to_output_spline(const Spline &input_spline,
+                                         Span<float> index_factors,
+                                         const VArray<T> &input_data,
+                                         MutableSpan<T> output_data)
+{
+  BLI_assert(input_data.size() == input_spline.evaluated_points_size());
+
+  parallel_for(output_data.index_range(), 1024, [&](IndexRange range) {
+    for (const int i : range) {
+      const Spline::LookupResult interp = input_spline.lookup_data_from_index_factor(
+          index_factors[i]);
+      output_data[i] = blender::attribute_math::mix2(interp.factor,
+                                                     input_data[interp.evaluated_index],
+                                                     input_data[interp.next_evaluated_index]);
+    }
+  });
+}
+
+static SplinePtr resample_spline(const Spline &input_spline, const int count)
+{
+  std::unique_ptr<PolySpline> output_spline = std::make_unique<PolySpline>();
+  output_spline->set_cyclic(input_spline.is_cyclic());
+  output_spline->normal_mode = input_spline.normal_mode;
+  output_spline->resize(count);
+
+  Array<float> uniform_samples = input_spline.sample_uniform_index_factors(count);
+
+  {
+    GVArray_For_Span positions(input_spline.evaluated_positions());
+    GVArray_Typed<float3> positions_typed(positions);
+    sample_span_to_output_spline<float3>(
+        input_spline, uniform_samples, positions_typed, output_spline->positions());
+  }
+  {
+    GVArrayPtr interpolated_data = input_spline.interpolate_to_evaluated_points(
+        GVArray_For_Span(input_spline.radii()));
+    GVArray_Typed<float> interpolated_data_typed{*interpolated_data};
+    sample_span_to_output_spline<float>(
+        input_spline, uniform_samples, interpolated_data_typed, output_spline->radii());
+  }
+  {
+    GVArrayPtr interpolated_data = input_spline.interpolate_to_evaluated_points(
+        GVArray_For_Span(input_spline.tilts()));
+    GVArray_Typed<float> interpolated_data_typed{*interpolated_data};
+    sample_span_to_output_spline<float>(
+        input_spline, uniform_samples, interpolated_data_typed, output_spline->tilts());
+  }
+
+  return output_spline;
+}
+
+static std::unique_ptr<CurveEval> resample_curve(const CurveEval &input_curve,
+                                                 const SampleModeParam &mode_param)
+{
+  std::unique_ptr<CurveEval> output_curve = std::make_unique<CurveEval>();
+
+  for (const SplinePtr &spline : input_curve.splines) {
+    if (mode_param.mode == GEO_NODE_CURVE_SAMPLE_COUNT) {
+      BLI_assert(mode_param.count);
+      output_curve->splines.append(resample_spline(*spline, *mode_param.count));
+    }
+    else if (mode_param.mode == GEO_NODE_CURVE_SAMPLE_LENGTH) {
+      BLI_assert(mode_param.length);
+      const float length = spline->length();
+      const int count = length / *mode_param.length;
+      output_curve->splines.append(resample_spline(*spline, count));
+    }
+  }
+
+  return output_curve;
+}
+
+static void geo_node_resample_exec(GeoNodeExecParams params)
+{
+  GeometrySet geometry_set = params.extract_input<GeometrySet>("Geometry");
+
+  geometry_set = bke::geometry_set_realize_instances(geometry_set);
+
+  if (!geometry_set.has_curve()) {
+    params.set_output("Geometry", GeometrySet());
+    return;
+  }
+
+  const CurveEval &input_curve = *geometry_set.get_curve_for_read();
+  NodeGeometryCurveResample &node_storage = *(NodeGeometryCurveResample *)params.node().storage;
+  const GeometryNodeCurveSampleMode mode = (GeometryNodeCurveSampleMode)node_storage.mode;
+  SampleModeParam mode_param;
+  mode_param.mode = mode;
+  if (mode == GEO_NODE_CURVE_SAMPLE_COUNT) {
+    const int count = params.extract_input<int>("Count");
+    if (count < 1) {
+      params.set_output("Geometry", GeometrySet());
+      return;
+    }
+    mode_param.count.emplace(count);
+  }
+  else if (mode == GEO_NODE_CURVE_SAMPLE_LENGTH) {
+    /* Don't allow asymptotic count increase for low resolution values. */
+    const float resolution = std::max(params.extract_input<float>("Length"), 0.0001f);
+    mode_param.length.emplace(resolution);
+  }
+
+  std::unique_ptr<CurveEval> output_curve = resample_curve(input_curve, mode_param);
+
+  params.set_output("Geometry", GeometrySet::create_with_curve(output_curve.release()));
+}
+
+}  // namespace blender::nodes
+
+void register_node_type_geo_curve_resample()
+{
+  static bNodeType ntype;
+
+  geo_node_type_base(&ntype, GEO_NODE_CURVE_RESAMPLE, "Resample Curve", NODE_CLASS_GEOMETRY, 0);
+  node_type_socket_templates(&ntype, geo_node_curve_resample_in, geo_node_curve_resample_out);
+  ntype.draw_buttons = geo_node_curve_resample_layout;
+  node_type_storage(
+      &ntype, "NodeGeometryCurveResample", node_free_standard_storage, node_copy_standard_storage);
+  node_type_init(&ntype, geo_node_curve_resample_init);
+  node_type_update(&ntype, geo_node_curve_resample_update);
+  ntype.geometry_node_execute = blender::nodes::geo_node_resample_exec;
+  nodeRegisterType(&ntype);
+}