Geometry Nodes: Curve Parameter Node

This commit adds a field input node that outputs the fraction of the
total length of the spline on each control point. This is useful for
anything that involves varying a value depending on how far along
the spline it is.

It also works when evaluated on the spline domain, where it outputs
the fraction of the total length of all of the splines at the start.

The operation isn't as well defined for NURB splines for the reasons
noted in the code comment. That can be said explicitly in the docs.

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

7 files changed, 212 insertions, 0 deletions

diff --git a/release/scripts/startup/nodeitems_builtins.py b/release/scripts/startup/nodeitems_builtins.py
index 5ec1db0baf8..77ffb609dd2 100644
--- a/release/scripts/startup/nodeitems_builtins.py
+++ b/release/scripts/startup/nodeitems_builtins.py
@@ -527,6 +527,7 @@ geometry_node_categories = [
         NodeItem("GeometryNodeCurveFill"),
         NodeItem("GeometryNodeCurveTrim"),
         NodeItem("GeometryNodeCurveLength"),
+        NodeItem("GeometryNodeCurveParameter", poll=geometry_nodes_fields_poll),
         NodeItem("GeometryNodeInputTangent", poll=geometry_nodes_fields_poll),
         NodeItem("GeometryNodeCurveSample", poll=geometry_nodes_fields_poll),
     ]),
diff --git a/source/blender/blenkernel/BKE_node.h b/source/blender/blenkernel/BKE_node.h
index e242aed879f..42e2cda8de3 100644
--- a/source/blender/blenkernel/BKE_node.h
+++ b/source/blender/blenkernel/BKE_node.h
@@ -1498,6 +1498,7 @@ int ntreeTexExecTree(struct bNodeTree *ntree,
 #define GEO_NODE_CURVE_SAMPLE 1085
 #define GEO_NODE_INPUT_TANGENT 1086
 #define GEO_NODE_STRING_JOIN 1087
+#define GEO_NODE_CURVE_PARAMETER 1088
 
 /** \} */
 
diff --git a/source/blender/blenkernel/intern/node.cc b/source/blender/blenkernel/intern/node.cc
index 7f423e53161..2d0239740f8 100644
--- a/source/blender/blenkernel/intern/node.cc
+++ b/source/blender/blenkernel/intern/node.cc
@@ -5187,6 +5187,7 @@ static void registerGeometryNodes()
   register_node_type_geo_curve_endpoints();
   register_node_type_geo_curve_fill();
   register_node_type_geo_curve_length();
+  register_node_type_geo_curve_parameter();
   register_node_type_geo_curve_primitive_bezier_segment();
   register_node_type_geo_curve_primitive_circle();
   register_node_type_geo_curve_primitive_line();
diff --git a/source/blender/nodes/CMakeLists.txt b/source/blender/nodes/CMakeLists.txt
index 1f6f1f333f0..a8795649ede 100644
--- a/source/blender/nodes/CMakeLists.txt
+++ b/source/blender/nodes/CMakeLists.txt
@@ -177,6 +177,7 @@ set(SRC
   geometry/nodes/node_geo_curve_endpoints.cc
   geometry/nodes/node_geo_curve_fill.cc
   geometry/nodes/node_geo_curve_length.cc
+  geometry/nodes/node_geo_curve_parameter.cc
   geometry/nodes/node_geo_curve_primitive_bezier_segment.cc
   geometry/nodes/node_geo_curve_primitive_circle.cc
   geometry/nodes/node_geo_curve_primitive_line.cc
diff --git a/source/blender/nodes/NOD_geometry.h b/source/blender/nodes/NOD_geometry.h
index 91d79d9e7b6..24f60263d8a 100644
--- a/source/blender/nodes/NOD_geometry.h
+++ b/source/blender/nodes/NOD_geometry.h
@@ -59,6 +59,7 @@ void register_node_type_geo_convex_hull(void);
 void register_node_type_geo_curve_endpoints(void);
 void register_node_type_geo_curve_fill(void);
 void register_node_type_geo_curve_length(void);
+void register_node_type_geo_curve_parameter(void);
 void register_node_type_geo_curve_sample(void);
 void register_node_type_geo_curve_primitive_bezier_segment(void);
 void register_node_type_geo_curve_primitive_circle(void);
diff --git a/source/blender/nodes/NOD_static_types.h b/source/blender/nodes/NOD_static_types.h
index 908940be93a..8fb18e839a7 100644
--- a/source/blender/nodes/NOD_static_types.h
+++ b/source/blender/nodes/NOD_static_types.h
@@ -319,6 +319,7 @@ DefNode(GeometryNode, GEO_NODE_CURVE_SAMPLE, def_geo_curve_sample, "CURVE_SAMPLE
 DefNode(GeometryNode, GEO_NODE_CURVE_ENDPOINTS, 0, "CURVE_ENDPOINTS", CurveEndpoints, "Curve Endpoints", "")
 DefNode(GeometryNode, GEO_NODE_CURVE_FILL, def_geo_curve_fill, "CURVE_FILL", CurveFill, "Curve Fill", "")
 DefNode(GeometryNode, GEO_NODE_CURVE_LENGTH, 0, "CURVE_LENGTH", CurveLength, "Curve Length", "")
+DefNode(GeometryNode, GEO_NODE_CURVE_PARAMETER, 0, "CURVE_PARAMETER", CurveParameter, "Curve Parameter", "")
 DefNode(GeometryNode, GEO_NODE_CURVE_PRIMITIVE_BEZIER_SEGMENT, def_geo_curve_primitive_bezier_segment, "CURVE_PRIMITIVE_BEZIER_SEGMENT", CurvePrimitiveBezierSegment, "Bezier Segment", "")
 DefNode(GeometryNode, GEO_NODE_CURVE_PRIMITIVE_CIRCLE, def_geo_curve_primitive_circle, "CURVE_PRIMITIVE_CIRCLE", CurvePrimitiveCircle, "Curve Circle", "")
 DefNode(GeometryNode, GEO_NODE_CURVE_PRIMITIVE_LINE, def_geo_curve_primitive_line, "CURVE_PRIMITIVE_LINE", CurvePrimitiveLine, "Curve Line", "")
diff --git a/source/blender/nodes/geometry/nodes/node_geo_curve_parameter.cc b/source/blender/nodes/geometry/nodes/node_geo_curve_parameter.cc
new file mode 100644
index 00000000000..2cde198e679
--- /dev/null
+++ b/source/blender/nodes/geometry/nodes/node_geo_curve_parameter.cc
@@ -0,0 +1,206 @@
+/*
+ * 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 "BKE_spline.hh"
+
+#include "node_geometry_util.hh"
+
+namespace blender::nodes {
+
+static void geo_node_curve_parameter_declare(NodeDeclarationBuilder &b)
+{
+  b.add_output<decl::Float>("Factor");
+}
+
+/**
+ * A basic interpolation from the point domain to the spline domain would be useless, since the
+ * average parameter for each spline would just be 0.5, or close to it. Instead, the parameter for
+ * each spline is the portion of the total length at the start of the spline.
+ */
+static Array<float> curve_parameter_spline_domain(const CurveEval &curve, const IndexMask mask)
+{
+  Span<SplinePtr> splines = curve.splines();
+  float length = 0.0f;
+  Array<float> parameters(splines.size());
+  for (const int i : splines.index_range()) {
+    parameters[i] = length;
+    length += splines[i]->length();
+  }
+  const float total_length_inverse = length == 0.0f ? 0.0f : 1.0f / length;
+  mask.foreach_index([&](const int64_t i) { parameters[i] *= total_length_inverse; });
+
+  return parameters;
+}
+
+/**
+ * The parameter at each control point is the factor at the corresponding evaluated point.
+ */
+static void calculate_bezier_parameters(const BezierSpline &spline, MutableSpan<float> parameters)
+{
+  Span<int> offsets = spline.control_point_offsets();
+  Span<float> lengths = spline.evaluated_lengths();
+  const float total_length = spline.length();
+  const float total_length_inverse = total_length == 0.0f ? 0.0f : 1.0f / total_length;
+
+  for (const int i : IndexRange(1, spline.size() - 1)) {
+    parameters[i] = lengths[offsets[i] - 1] * total_length_inverse;
+  }
+}
+
+/**
+ * The parameter for poly splines is simply the evaluated lengths divided by the total length.
+ */
+static void calculate_poly_parameters(const PolySpline &spline, MutableSpan<float> parameters)
+{
+  Span<float> lengths = spline.evaluated_lengths();
+  const float total_length = spline.length();
+  const float total_length_inverse = total_length == 0.0f ? 0.0f : 1.0f / total_length;
+
+  for (const int i : IndexRange(1, spline.size() - 1)) {
+    parameters[i] = lengths[i - 1] * total_length_inverse;
+  }
+}
+
+/**
+ * Since NURBS control points do not necessarily coincide with the evaluated curve's path, and
+ * each control point doesn't correspond well to a specific evaluated point, the parameter at
+ * each point is not well defined. So instead, treat the control points as if they were a poly
+ * spline.
+ */
+static void calculate_nurbs_parameters(const NURBSpline &spline, MutableSpan<float> parameters)
+{
+  Span<float3> positions = spline.positions();
+  Array<float> control_point_lengths(spline.size());
+
+  float length = 0.0f;
+  for (const int i : IndexRange(positions.size() - 1)) {
+    parameters[i] = length;
+    length += float3::distance(positions[i], positions[i + 1]);
+  }
+
+  const float total_length_inverse = length == 0.0f ? 0.0f : 1.0f / length;
+  for (float &parameter : parameters) {
+    parameter *= total_length_inverse;
+  }
+}
+
+static Array<float> curve_parameter_point_domain(const CurveEval &curve)
+{
+  Span<SplinePtr> splines = curve.splines();
+  Array<int> offsets = curve.control_point_offsets();
+  const int total_size = offsets.last();
+  Array<float> parameters(total_size);
+
+  threading::parallel_for(splines.index_range(), 128, [&](IndexRange range) {
+    for (const int i : range) {
+      const Spline &spline = *splines[i];
+      MutableSpan spline_factors{parameters.as_mutable_span().slice(offsets[i], spline.size())};
+      spline_factors.first() = 0.0f;
+      switch (splines[i]->type()) {
+        case Spline::Type::Bezier: {
+          calculate_bezier_parameters(static_cast<const BezierSpline &>(spline), spline_factors);
+          break;
+        }
+        case Spline::Type::Poly: {
+          calculate_poly_parameters(static_cast<const PolySpline &>(spline), spline_factors);
+          break;
+        }
+        case Spline::Type::NURBS: {
+          calculate_nurbs_parameters(static_cast<const NURBSpline &>(spline), spline_factors);
+          break;
+        }
+      }
+    }
+  });
+  return parameters;
+}
+
+static const GVArray *construct_curve_parameter_gvarray(const CurveEval &curve,
+                                                        const IndexMask mask,
+                                                        const AttributeDomain domain,
+                                                        ResourceScope &scope)
+{
+  if (domain == ATTR_DOMAIN_POINT) {
+    Array<float> parameters = curve_parameter_point_domain(curve);
+    return &scope.construct<fn::GVArray_For_ArrayContainer<Array<float>>>(std::move(parameters));
+  }
+
+  if (domain == ATTR_DOMAIN_CURVE) {
+    Array<float> parameters = curve_parameter_spline_domain(curve, mask);
+    return &scope.construct<fn::GVArray_For_ArrayContainer<Array<float>>>(std::move(parameters));
+  }
+
+  return nullptr;
+}
+
+class CurveParameterFieldInput final : public fn::FieldInput {
+ public:
+  CurveParameterFieldInput() : fn::FieldInput(CPPType::get<float>(), "Curve Parameter")
+  {
+  }
+
+  const GVArray *get_varray_for_context(const fn::FieldContext &context,
+                                        IndexMask mask,
+                                        ResourceScope &scope) const final
+  {
+    if (const GeometryComponentFieldContext *geometry_context =
+            dynamic_cast<const GeometryComponentFieldContext *>(&context)) {
+
+      const GeometryComponent &component = geometry_context->geometry_component();
+      const AttributeDomain domain = geometry_context->domain();
+
+      if (component.type() == GEO_COMPONENT_TYPE_CURVE) {
+        const CurveComponent &curve_component = static_cast<const CurveComponent &>(component);
+        const CurveEval *curve = curve_component.get_for_read();
+        if (curve) {
+          return construct_curve_parameter_gvarray(*curve, mask, domain, scope);
+        }
+      }
+    }
+    return nullptr;
+  }
+
+  uint64_t hash() const override
+  {
+    /* Some random constant hash. */
+    return 29837456298;
+  }
+
+  bool is_equal_to(const fn::FieldNode &other) const override
+  {
+    return dynamic_cast<const CurveParameterFieldInput *>(&other) != nullptr;
+  }
+};
+
+static void geo_node_curve_parameter_exec(GeoNodeExecParams params)
+{
+  Field<float> parameter_field{std::make_shared<CurveParameterFieldInput>()};
+  params.set_output("Factor", std::move(parameter_field));
+}
+
+}  // namespace blender::nodes
+
+void register_node_type_geo_curve_parameter()
+{
+  static bNodeType ntype;
+
+  geo_node_type_base(&ntype, GEO_NODE_CURVE_PARAMETER, "Curve Parameter", NODE_CLASS_INPUT, 0);
+  ntype.geometry_node_execute = blender::nodes::geo_node_curve_parameter_exec;
+  ntype.declare = blender::nodes::geo_node_curve_parameter_declare;
+  nodeRegisterType(&ntype);
+}