Geometry Nodes: Port the trim curve node to the new data-block

The trim functionality is implemented in the geometry module, and
generalized a bit to be potentially useful for bisecting in the future.
The implementation is based on a helper type called `IndexRangeCyclic`
which allows iteration over all control points between two points on a
curve.

Catmull Rom curves are now supported-- trimmed without resampling first.
However, maintaining the exact shape is not possible. NURBS splines are
still converted to polylines using the evaluated curve concept.

Performance is equivalent or faster then a 3.1 build with regards to
node timings. Compared to 3.3 and 3.2, it's easy to observe test cases
where the node is at least 3 or 4 times faster.

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

1 files changed, 71 insertions, 2 deletions

diff --git a/source/blender/blenkernel/BKE_curves.hh b/source/blender/blenkernel/BKE_curves.hh
index 4b0fc293b54..9f150c13d6e 100644
--- a/source/blender/blenkernel/BKE_curves.hh
+++ b/source/blender/blenkernel/BKE_curves.hh
@@ -22,6 +22,7 @@
 #include "BLI_virtual_array.hh"
 
 #include "BKE_attribute.hh"
+#include "BKE_attribute_math.hh"
 
 namespace blender::bke {
 
@@ -162,6 +163,11 @@ class CurvesGeometry : public ::CurvesGeometry {
   IndexRange curves_range() const;
 
   /**
+   * Number of control points in the indexed curve.
+   */
+  int points_num_for_curve(const int index) const;
+
+  /**
    * The index of the first point in every curve. The size of this span is one larger than the
    * number of curves. Consider using #points_for_curve rather than using the offsets directly.
    */
@@ -532,6 +538,16 @@ bool segment_is_vector(Span<int8_t> handle_types_left,
                        int segment_index);
 
 /**
+ * True if the Bezier curve contains polygonal segments of HandleType::BEZIER_HANDLE_VECTOR.
+ *
+ * \param num_curve_points: Number of points in the curve.
+ * \param evaluated_size: Number of evaluated points in the curve.
+ * \param cyclic: If curve is cyclic.
+ * \param resolution: Curve resolution.
+ */
+bool has_vector_handles(int num_curve_points, int64_t evaluated_size, bool cyclic, int resolution);
+
+/**
  * Return true if the curve's last cyclic segment has a vector type.
  * This only makes a difference in the shape of cyclic curves.
  */
@@ -693,6 +709,36 @@ void interpolate_to_evaluated(const GSpan src,
                               const Span<int> evaluated_offsets,
                               GMutableSpan dst);
 
+void calculate_basis(const float parameter, float r_weights[4]);
+
+/**
+ * Interpolate the control point values for the given parameter on the piecewise segment.
+ * \param a: Value associated with the first control point influencing the segment.
+ * \param d: Value associated with the fourth control point.
+ * \param parameter: Parameter in range [0, 1] to compute the interpolation for.
+ */
+template<typename T>
+T interpolate(const T &a, const T &b, const T &c, const T &d, const float parameter)
+{
+  float n[4];
+  calculate_basis(parameter, n);
+  /* TODO: Use DefaultMixer or other generic mixing in the basis evaluation function to simplify
+   * supporting more types. */
+  if constexpr (!is_same_any_v<T, float, float2, float3, float4, int8_t, int, int64_t>) {
+    T return_value;
+    attribute_math::DefaultMixer<T> mixer({&return_value, 1});
+    mixer.mix_in(0, a, n[0] * 0.5f);
+    mixer.mix_in(0, b, n[1] * 0.5f);
+    mixer.mix_in(0, c, n[2] * 0.5f);
+    mixer.mix_in(0, d, n[3] * 0.5f);
+    mixer.finalize();
+    return return_value;
+  }
+  else {
+    return 0.5f * (a * n[0] + b * n[1] + c * n[2] + d * n[3]);
+  }
+}
+
 }  // namespace catmull_rom
 
 /** \} */
@@ -807,6 +853,16 @@ inline IndexRange CurvesGeometry::curves_range() const
   return IndexRange(this->curves_num());
 }
 
+inline int CurvesGeometry::points_num_for_curve(const int index) const
+{
+  BLI_assert(this->curve_num > 0);
+  BLI_assert(this->curve_num > index);
+  BLI_assert(this->curve_offsets != nullptr);
+  const int offset = this->curve_offsets[index];
+  const int offset_next = this->curve_offsets[index + 1];
+  return offset_next - offset;
+}
+
 inline bool CurvesGeometry::is_single_type(const CurveType type) const
 {
   return this->curve_type_counts()[type] == this->curves_num();
@@ -833,6 +889,7 @@ inline IndexRange CurvesGeometry::points_for_curve(const int index) const
 {
   /* Offsets are not allocated when there are no curves. */
   BLI_assert(this->curve_num > 0);
+  BLI_assert(this->curve_num > index);
   BLI_assert(this->curve_offsets != nullptr);
   const int offset = this->curve_offsets[index];
   const int offset_next = this->curve_offsets[index + 1];
@@ -905,11 +962,13 @@ inline float CurvesGeometry::evaluated_length_total_for_curve(const int curve_in
 
 /** \} */
 
+namespace curves {
+
 /* -------------------------------------------------------------------- */
 /** \name Bezier Inline Methods
  * \{ */
 
-namespace curves::bezier {
+namespace bezier {
 
 inline bool point_is_sharp(const Span<int8_t> handle_types_left,
                            const Span<int8_t> handle_types_right,
@@ -929,14 +988,24 @@ inline bool segment_is_vector(const int8_t left, const int8_t right)
   return segment_is_vector(HandleType(left), HandleType(right));
 }
 
+inline bool has_vector_handles(const int num_curve_points,
+                               const int64_t evaluated_size,
+                               const bool cyclic,
+                               const int resolution)
+{
+  return evaluated_size - !cyclic != (int64_t)segments_num(num_curve_points, cyclic) * resolution;
+}
+
 inline float3 calculate_vector_handle(const float3 &point, const float3 &next_point)
 {
   return math::interpolate(point, next_point, 1.0f / 3.0f);
 }
 
+}  // namespace bezier
+
 /** \} */
 
-}  // namespace curves::bezier
+}  // namespace curves
 
 struct CurvesSurfaceTransforms {
   float4x4 curves_to_world;