Geometry Nodes: Curve Subdivide Node with Fields

The curve subdivide node can now take an int field to specify the
number of subdivisions to make at each curve segment.

Reviewed by: Hans Goudey
Differential Revision: https://developer.blender.org/D12534

release/scripts/startup/nodeitems_builtins.py

@@ -525,6 +525,7 @@ geometry_node_categories = [
         NodeItem("GeometryNodeCurveFill"),
         NodeItem("GeometryNodeCurveTrim"),
         NodeItem("GeometryNodeCurveLength"),
+        NodeItem("GeometryNodeCurveSubdivide"),
         NodeItem("GeometryNodeCurveParameter"),
         NodeItem("GeometryNodeInputTangent"),
         NodeItem("GeometryNodeCurveSample"),

source/blender/blenkernel/BKE_node.h

@@ -1509,6 +1509,7 @@ int ntreeTexExecTree(struct bNodeTree *ntree,
 #define GEO_NODE_CURVE_REVERSE 1095
 #define GEO_NODE_PROXIMITY 1096
 
+#define GEO_NODE_CURVE_SUBDIVIDE 1097
 /** \} */
 
 /* -------------------------------------------------------------------- */

source/blender/blenkernel/intern/node.cc

@@ -5714,6 +5714,7 @@ static void registerGeometryNodes()
   register_node_type_geo_legacy_material_assign();
   register_node_type_geo_legacy_select_by_material();
   register_node_type_geo_legacy_curve_reverse();
+  register_node_type_geo_legacy_curve_subdivide();
 
   register_node_type_geo_align_rotation_to_vector();
   register_node_type_geo_attribute_capture();

source/blender/makesrna/intern/rna_nodetree.c

@@ -10280,7 +10280,7 @@ static void def_geo_curve_resample(StructRNA *srna)
   RNA_def_property_update(prop, NC_NODE | NA_EDITED, "rna_Node_socket_update");
 }
 
-static void def_geo_curve_subdivide(StructRNA *srna)
+static void def_geo_legacy_curve_subdivide(StructRNA *srna)
 {
   PropertyRNA *prop;
 

source/blender/nodes/CMakeLists.txt

@@ -209,6 +209,7 @@ set(SRC
   geometry/nodes/node_geo_curve_resample.cc
   geometry/nodes/node_geo_curve_reverse.cc
   geometry/nodes/node_geo_curve_sample.cc
+  geometry/nodes/node_geo_curve_subdivide.cc
   geometry/nodes/node_geo_curve_to_mesh.cc
   geometry/nodes/node_geo_curve_trim.cc
   geometry/nodes/node_geo_distribute_points_on_faces.cc

source/blender/nodes/NOD_geometry.h

@@ -34,6 +34,7 @@ void register_node_type_geo_legacy_attribute_randomize(void);
 void register_node_type_geo_legacy_material_assign(void);
 void register_node_type_geo_legacy_select_by_material(void);
 void register_node_type_geo_legacy_curve_reverse(void);
+void register_node_type_geo_legacy_curve_subdivide(void);
 
 void register_node_type_geo_align_rotation_to_vector(void);
 void register_node_type_geo_attribute_capture(void);

source/blender/nodes/NOD_static_types.h

@@ -299,7 +299,7 @@ DefNode(GeometryNode, GEO_NODE_LEGACY_CURVE_REVERSE, 0, "LEGACY_CURVE_REVERSE",
 DefNode(GeometryNode, GEO_NODE_LEGACY_CURVE_SELECT_HANDLES, def_geo_curve_select_handles, "LEGACY_CURVE_SELECT_HANDLES", LegacyCurveSelectHandles, "Select by Handle Type", "")
 DefNode(GeometryNode, GEO_NODE_LEGACY_CURVE_SET_HANDLES, def_geo_curve_set_handles, "LEGACY_CURVE_SET_HANDLES", LegacyCurveSetHandles, "Set Handle Type", "")
 DefNode(GeometryNode, GEO_NODE_LEGACY_CURVE_SPLINE_TYPE, def_geo_curve_spline_type, "LEGACY_CURVE_SPLINE_TYPE", LegacyCurveSplineType, "Set Spline Type", "")
-DefNode(GeometryNode, GEO_NODE_LEGACY_CURVE_SUBDIVIDE, def_geo_curve_subdivide, "LEGACY_CURVE_SUBDIVIDE", LegacyCurveSubdivide, "Curve Subdivide", "")
+DefNode(GeometryNode, GEO_NODE_LEGACY_CURVE_SUBDIVIDE, def_geo_legacy_curve_subdivide, "LEGACY_CURVE_SUBDIVIDE", LegacyCurveSubdivide, "Curve Subdivide", "")
 DefNode(GeometryNode, GEO_NODE_LEGACY_CURVE_TO_POINTS, def_geo_curve_to_points, "LEGACY_CURVE_TO_POINTS", LegacyCurveToPoints, "Curve to Points", "")
 DefNode(GeometryNode, GEO_NODE_LEGACY_DELETE_GEOMETRY, 0, "LEGACY_DELETE_GEOMETRY", LegacyDeleteGeometry, "Delete Geometry", "")
 DefNode(GeometryNode, GEO_NODE_LEGACY_EDGE_SPLIT, 0, "LEGACY_EDGE_SPLIT", LegacyEdgeSplit, "Edge Split", "")
@@ -337,6 +337,7 @@ DefNode(GeometryNode, GEO_NODE_CURVE_PRIMITIVE_STAR, 0, "CURVE_PRIMITIVE_STAR",
 DefNode(GeometryNode, GEO_NODE_CURVE_RESAMPLE, def_geo_curve_resample, "CURVE_RESAMPLE", CurveResample, "Resample Curve", "")
 DefNode(GeometryNode, GEO_NODE_CURVE_REVERSE, 0, "CURVE_REVERSE", CurveReverse, "Curve Reverse", "")
 DefNode(GeometryNode, GEO_NODE_CURVE_SAMPLE, def_geo_curve_sample, "CURVE_SAMPLE", CurveSample, "Curve Sample", "")
+DefNode(GeometryNode, GEO_NODE_CURVE_SUBDIVIDE, 0, "CURVE_SUBDIVIDE", CurveSubdivide, "Curve Subdivide", "")
 DefNode(GeometryNode, GEO_NODE_CURVE_TO_MESH, 0, "CURVE_TO_MESH", CurveToMesh, "Curve to Mesh", "")
 DefNode(GeometryNode, GEO_NODE_CURVE_TRIM, def_geo_curve_trim, "CURVE_TRIM", CurveTrim, "Curve Trim", "")
 DefNode(GeometryNode, GEO_NODE_DISTRIBUTE_POINTS_ON_FACES, def_geo_distribute_points_on_faces, "DISTRIBUTE_POINTS_ON_FACES", DistributePointsOnFaces, "Distribute Points on Faces", "")

source/blender/nodes/geometry/nodes/legacy/node_geo_curve_subdivide.cc

@@ -373,7 +373,7 @@ static void geo_node_subdivide_exec(GeoNodeExecParams params)
 
 }  // namespace blender::nodes
 
-void register_node_type_geo_curve_subdivide()
+void register_node_type_geo_legacy_curve_subdivide()
 {
   static bNodeType ntype;
 

source/blender/nodes/geometry/nodes/node_geo_curve_subdivide.cc

@@ -0,0 +1,364 @@
+/*
+ * 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_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_GSpan;
+using blender::fn::GVArray_For_Span;
+using blender::fn::GVArray_Typed;
+
+namespace blender::nodes {
+
+static void geo_node_curve_subdivide_declare(NodeDeclarationBuilder &b)
+{
+  b.add_input<decl::Geometry>("Geometry");
+  b.add_input<decl::Int>("Cuts").default_value(1).min(0).max(1000).supports_field();
+  b.add_output<decl::Geometry>("Geometry");
+}
+
+static Array<int> get_subdivided_offsets(const Spline &spline,
+                                         const VArray<int> &cuts,
+                                         const int spline_offset)
+{
+  Array<int> offsets(spline.segments_size() + 1);
+  int offset = 0;
+  for (const int i : IndexRange(spline.segments_size())) {
+    offsets[i] = offset;
+    offset = offset + std::max(cuts[spline_offset + i], 0) + 1;
+  }
+  offsets.last() = offset;
+  return offsets;
+}
+
+template<typename T>
+static void subdivide_attribute(Span<T> src,
+                                const Span<int> offsets,
+                                const bool is_cyclic,
+                                MutableSpan<T> dst)
+{
+  const int src_size = src.size();
+  threading::parallel_for(IndexRange(src_size - 1), 1024, [&](IndexRange range) {
+    for (const int i : range) {
+      const int cuts = offsets[i + 1] - offsets[i];
+      dst[offsets[i]] = src[i];
+      const float factor_delta = 1.0f / (cuts + 1.0f);
+      for (const int cut : IndexRange(cuts)) {
+        const float factor = (cut + 1) * factor_delta;
+        dst[offsets[i] + cut] = attribute_math::mix2(factor, src[i], src[i + 1]);
+      }
+    }
+  });
+
+  if (is_cyclic) {
+    const int i = src_size - 1;
+    const int cuts = offsets[i + 1] - offsets[i];
+    dst[offsets[i]] = src.last();
+    const float factor_delta = 1.0f / (cuts + 1.0f);
+    for (const int cut : IndexRange(cuts)) {
+      const float factor = (cut + 1) * factor_delta;
+      dst[offsets[i] + cut] = attribute_math::mix2(factor, src.last(), src.first());
+    }
+  }
+  else {
+    dst.last() = src.last();
+  }
+}
+
+/**
+ * In order to generate a Bezier spline with the same shape as the input spline, apply the
+ * De Casteljau algorithm iteratively for the provided number of cuts, constantly updating the
+ * previous result point's right handle and the left handle at the end of the segment.
+ *
+ * \note Non-vector segments in the result spline are given free handles. This could possibly be
+ * improved with another pass that sets handles to aligned where possible, but currently that does
+ * not provide much benefit for the increased complexity.
+ */
+static void subdivide_bezier_segment(const BezierSpline &src,
+                                     const int index,
+                                     const int offset,
+                                     const int result_size,
+                                     Span<float3> src_positions,
+                                     Span<float3> src_handles_left,
+                                     Span<float3> src_handles_right,
+                                     MutableSpan<float3> dst_positions,
+                                     MutableSpan<float3> dst_handles_left,
+                                     MutableSpan<float3> dst_handles_right,
+                                     MutableSpan<BezierSpline::HandleType> dst_type_left,
+                                     MutableSpan<BezierSpline::HandleType> dst_type_right)
+{
+  const bool is_last_cyclic_segment = index == (src.size() - 1);
+  const int next_index = is_last_cyclic_segment ? 0 : index + 1;
+
+  /* The first point in the segment is always copied. */
+  dst_positions[offset] = src_positions[index];
+
+  if (src.segment_is_vector(index)) {
+    if (is_last_cyclic_segment) {
+      dst_type_left.first() = BezierSpline::HandleType::Vector;
+    }
+    dst_type_left.slice(offset + 1, result_size).fill(BezierSpline::HandleType::Vector);
+    dst_type_right.slice(offset, result_size).fill(BezierSpline::HandleType::Vector);
+
+    const float factor_delta = 1.0f / result_size;
+    for (const int cut : IndexRange(result_size)) {
+      const float factor = cut * factor_delta;
+      dst_positions[offset + cut] = attribute_math::mix2(
+          factor, src_positions[index], src_positions[next_index]);
+    }
+  }
+  else {
+    if (is_last_cyclic_segment) {
+      dst_type_left.first() = BezierSpline::HandleType::Free;
+    }
+    dst_type_left.slice(offset + 1, result_size).fill(BezierSpline::HandleType::Free);
+    dst_type_right.slice(offset, result_size).fill(BezierSpline::HandleType::Free);
+
+    const int i_segment_last = is_last_cyclic_segment ? 0 : offset + result_size;
+
+    /* Create a Bezier segment to update iteratively for every subdivision
+     * and references to the meaningful values for ease of use. */
+    BezierSpline temp;
+    temp.resize(2);
+    float3 &segment_start = temp.positions().first();
+    float3 &segment_end = temp.positions().last();
+    float3 &handle_prev = temp.handle_positions_right().first();
+    float3 &handle_next = temp.handle_positions_left().last();
+    segment_start = src_positions[index];
+    segment_end = src_positions[next_index];
+    handle_prev = src_handles_right[index];
+    handle_next = src_handles_left[next_index];
+
+    for (const int cut : IndexRange(result_size - 1)) {
+      const float parameter = 1.0f / (result_size - cut);
+      const BezierSpline::InsertResult insert = temp.calculate_segment_insertion(0, 1, parameter);
+
+      /* Copy relevant temporary data to the result. */
+      dst_handles_right[offset + cut] = insert.handle_prev;
+      dst_handles_left[offset + cut + 1] = insert.left_handle;
+      dst_positions[offset + cut + 1] = insert.position;
+
+      /* Update the segment to prepare it for the next subdivision. */
+      segment_start = insert.position;
+      handle_prev = insert.right_handle;
+      handle_next = insert.handle_next;
+    }
+
+    /* Copy the handles for the last segment from the temporary spline. */
+    dst_handles_right[offset + result_size - 1] = handle_prev;
+    dst_handles_left[i_segment_last] = handle_next;
+  }
+}
+
+static void subdivide_bezier_spline(const BezierSpline &src,
+                                    const Span<int> offsets,
+                                    BezierSpline &dst)
+{
+  Span<float3> src_positions = src.positions();
+  Span<float3> src_handles_left = src.handle_positions_left();
+  Span<float3> src_handles_right = src.handle_positions_right();
+  MutableSpan<float3> dst_positions = dst.positions();
+  MutableSpan<float3> dst_handles_left = dst.handle_positions_left();
+  MutableSpan<float3> dst_handles_right = dst.handle_positions_right();
+  MutableSpan<BezierSpline::HandleType> dst_type_left = dst.handle_types_left();
+  MutableSpan<BezierSpline::HandleType> dst_type_right = dst.handle_types_right();
+
+  threading::parallel_for(IndexRange(src.size() - 1), 512, [&](IndexRange range) {
+    for (const int i : range) {
+      subdivide_bezier_segment(src,
+                               i,
+                               offsets[i],
+                               offsets[i + 1] - offsets[i],
+                               src_positions,
+                               src_handles_left,
+                               src_handles_right,
+                               dst_positions,
+                               dst_handles_left,
+                               dst_handles_right,
+                               dst_type_left,
+                               dst_type_right);
+    }
+  });
+
+  if (src.is_cyclic()) {
+    const int i_last = src.size() - 1;
+    subdivide_bezier_segment(src,
+                             i_last,
+                             offsets[i_last],
+                             offsets.last() - offsets[i_last],
+                             src_positions,
+                             src_handles_left,
+                             src_handles_right,
+                             dst_positions,
+                             dst_handles_left,
+                             dst_handles_right,
+                             dst_type_left,
+                             dst_type_right);
+  }
+  else {
+    dst_positions.last() = src_positions.last();
+  }
+}
+
+static void subdivide_builtin_attributes(const Spline &src_spline,
+                                         const Span<int> offsets,
+                                         Spline &dst_spline)
+{
+  const bool is_cyclic = src_spline.is_cyclic();
+  subdivide_attribute<float>(src_spline.radii(), offsets, is_cyclic, dst_spline.radii());
+  subdivide_attribute<float>(src_spline.tilts(), offsets, is_cyclic, dst_spline.tilts());
+  switch (src_spline.type()) {
+    case Spline::Type::Poly: {
+      const PolySpline &src = static_cast<const PolySpline &>(src_spline);
+      PolySpline &dst = static_cast<PolySpline &>(dst_spline);
+      subdivide_attribute<float3>(src.positions(), offsets, is_cyclic, dst.positions());
+      break;
+    }
+    case Spline::Type::Bezier: {
+      const BezierSpline &src = static_cast<const BezierSpline &>(src_spline);
+      BezierSpline &dst = static_cast<BezierSpline &>(dst_spline);
+      subdivide_bezier_spline(src, offsets, dst);
+      dst.mark_cache_invalid();
+      break;
+    }
+    case Spline::Type::NURBS: {
+      const NURBSpline &src = static_cast<const NURBSpline &>(src_spline);
+      NURBSpline &dst = static_cast<NURBSpline &>(dst_spline);
+      subdivide_attribute<float3>(src.positions(), offsets, is_cyclic, dst.positions());
+      subdivide_attribute<float>(src.weights(), offsets, is_cyclic, dst.weights());
+      break;
+    }
+  }
+}
+
+static void subdivide_dynamic_attributes(const Spline &src_spline,
+                                         const Span<int> offsets,
+                                         Spline &dst_spline)
+{
+  const bool is_cyclic = src_spline.is_cyclic();
+  src_spline.attributes.foreach_attribute(
+      [&](const bke::AttributeIDRef &attribute_id, const AttributeMetaData &meta_data) {
+        std::optional<GSpan> src = src_spline.attributes.get_for_read(attribute_id);
+        BLI_assert(src);
+
+        if (!dst_spline.attributes.create(attribute_id, meta_data.data_type)) {
+          /* Since the source spline of the same type had the attribute, adding it should work. */
+          BLI_assert_unreachable();
+        }
+
+        std::optional<GMutableSpan> dst = dst_spline.attributes.get_for_write(attribute_id);
+        BLI_assert(dst);
+
+        attribute_math::convert_to_static_type(dst->type(), [&](auto dummy) {
+          using T = decltype(dummy);
+          subdivide_attribute<T>(src->typed<T>(), offsets, is_cyclic, dst->typed<T>());
+        });
+        return true;
+      },
+      ATTR_DOMAIN_POINT);
+}
+
+static SplinePtr subdivide_spline(const Spline &spline,
+                                  const VArray<int> &cuts,
+                                  const int spline_offset)
+{
+  /* Since we expect to access each value many times, it should be worth it to make sure the
+   * attribute is a real span (especially considering the note below). Using the offset at each
+   * point facilitates subdividing in parallel later. */
+  Array<int> offsets = get_subdivided_offsets(spline, cuts, spline_offset);
+  const int result_size = offsets.last() + int(!spline.is_cyclic());
+  SplinePtr new_spline = spline.copy_only_settings();
+  new_spline->resize(result_size);
+  subdivide_builtin_attributes(spline, offsets, *new_spline);
+  subdivide_dynamic_attributes(spline, offsets, *new_spline);
+  return new_spline;
+}
+
+/**
+ * \note Passing the virtual array for the entire spline is possibly quite inefficient here when
+ * the attribute was on the point domain and stored separately for each spline already, and it
+ * prevents some other optimizations like skipping splines with a single attribute value of < 1.
+ * However, it allows the node to access builtin attribute easily, so it the makes most sense this
+ * way until the attribute API is refactored.
+ */
+static std::unique_ptr<CurveEval> subdivide_curve(const CurveEval &input_curve,
+                                                  const VArray<int> &cuts)
+{
+  const Array<int> control_point_offsets = input_curve.control_point_offsets();
+  const Span<SplinePtr> input_splines = input_curve.splines();
+
+  std::unique_ptr<CurveEval> output_curve = std::make_unique<CurveEval>();
+  output_curve->resize(input_splines.size());
+  output_curve->attributes = input_curve.attributes;
+  MutableSpan<SplinePtr> output_splines = output_curve->splines();
+
+  threading::parallel_for(input_splines.index_range(), 128, [&](IndexRange range) {
+    for (const int i : range) {
+      output_splines[i] = subdivide_spline(*input_splines[i], cuts, control_point_offsets[i]);
+    }
+  });
+
+  return output_curve;
+}
+
+static void geo_node_subdivide_exec(GeoNodeExecParams params)
+{
+  GeometrySet geometry_set = params.extract_input<GeometrySet>("Geometry");
+  Field<int> cuts_field = params.extract_input<Field<int>>("Cuts");
+
+  geometry_set.modify_geometry_sets([&](GeometrySet &geometry_set) {
+    if (!geometry_set.has_curve()) {
+      return;
+    }
+
+    const CurveComponent &component = *geometry_set.get_component_for_read<CurveComponent>();
+    GeometryComponentFieldContext field_context{component, ATTR_DOMAIN_POINT};
+    const int domain_size = component.attribute_domain_size(ATTR_DOMAIN_POINT);
+
+    fn::FieldEvaluator evaluator{field_context, domain_size};
+    evaluator.add(cuts_field);
+    evaluator.evaluate();
+    const VArray<int> &cuts = evaluator.get_evaluated<int>(0);
+
+    if (cuts.is_single() && cuts.get_internal_single() < 1) {
+      return;
+    }
+
+    std::unique_ptr<CurveEval> output_curve = subdivide_curve(*component.get_for_read(), cuts);
+    geometry_set.replace_curve(output_curve.release());
+  });
+  params.set_output("Geometry", geometry_set);
+}
+
+}  // namespace blender::nodes
+
+void register_node_type_geo_curve_subdivide()
+{
+  static bNodeType ntype;
+
+  geo_node_type_base(&ntype, GEO_NODE_CURVE_SUBDIVIDE, "Curve Subdivide", NODE_CLASS_GEOMETRY, 0);
+  ntype.declare = blender::nodes::geo_node_curve_subdivide_declare;
+  ntype.geometry_node_execute = blender::nodes::geo_node_subdivide_exec;
+  nodeRegisterType(&ntype);
+}