Bezier Spline: Add a more generalized insertion utility

This logic is from the curve sundivide node, used to add points with
proper handles in between two existing points. However, the same logic
is used for trimming of Bezier splines, and possibly interactive point
insertion in the future, so it's helpful as a general utility.

The logic is converted to depend on a bezier spline instead of being
static. A temporary segment spline can be used for the latter use case.

3 files changed, 84 insertions, 44 deletions

diff --git a/source/blender/blenkernel/BKE_spline.hh b/source/blender/blenkernel/BKE_spline.hh
index 1aac2e311e3..f85e62768f7 100644
--- a/source/blender/blenkernel/BKE_spline.hh
+++ b/source/blender/blenkernel/BKE_spline.hh
@@ -337,6 +337,18 @@ class BezierSpline final : public Spline {
                         blender::MutableSpan<blender::float3> positions) const;
   bool segment_is_vector(const int start_index) const;
 
+  /** See comment and diagram for #calculate_segment_insertion. */
+  struct InsertResult {
+    blender::float3 handle_prev;
+    blender::float3 left_handle;
+    blender::float3 position;
+    blender::float3 right_handle;
+    blender::float3 handle_next;
+  };
+  InsertResult calculate_segment_insertion(const int index,
+                                           const int next_index,
+                                           const float parameter);
+
  private:
   void correct_end_tangents() const final;
   void copy_settings(Spline &dst) const final;
diff --git a/source/blender/blenkernel/intern/spline_bezier.cc b/source/blender/blenkernel/intern/spline_bezier.cc
index 02d26ac715b..b6764f65631 100644
--- a/source/blender/blenkernel/intern/spline_bezier.cc
+++ b/source/blender/blenkernel/intern/spline_bezier.cc
@@ -333,6 +333,46 @@ void BezierSpline::correct_end_tangents() const
   }
 }
 
+/**
+ * De Casteljau Bezier subdivision.
+ * \param index: The index of the segment's start control point.
+ * \param next_index: The index of the control point at the end of the segment. Could be 0,
+ * if the spline is cyclic.
+ * \param parameter: The factor along the segment, between 0 and 1. Note that this is used
+ * directly by the calculation, it doesn't correspond to a portion of the evaluated length.
+ *
+ * <pre>
+ *           handle_prev         handle_next
+ *                x----------------x
+ *               /                  \
+ *              /      x---O---x     \
+ *             /        result        \
+ *            /                        \
+ *           O                          O
+ *       point_prev                  point_next
+ * </pre>
+ */
+BezierSpline::InsertResult BezierSpline::calculate_segment_insertion(const int index,
+                                                                     const int next_index,
+                                                                     const float parameter)
+{
+  BLI_assert(parameter <= 1.0f && parameter >= 0.0f);
+  BLI_assert(next_index == 0 || next_index == index + 1);
+  const float3 &point_prev = positions_[index];
+  const float3 &handle_prev = handle_positions_right_[index];
+  const float3 &handle_next = handle_positions_left_[next_index];
+  const float3 &point_next = positions_[next_index];
+  const float3 center_point = float3::interpolate(handle_prev, handle_next, parameter);
+
+  BezierSpline::InsertResult result;
+  result.handle_prev = float3::interpolate(point_prev, handle_prev, parameter);
+  result.handle_next = float3::interpolate(handle_next, point_next, parameter);
+  result.left_handle = float3::interpolate(result.handle_prev, center_point, parameter);
+  result.right_handle = float3::interpolate(center_point, result.handle_next, parameter);
+  result.position = float3::interpolate(result.left_handle, result.right_handle, parameter);
+  return result;
+}
+
 static void bezier_forward_difference_3d(const float3 &point_0,
                                          const float3 &point_1,
                                          const float3 &point_2,
diff --git a/source/blender/nodes/geometry/nodes/node_geo_curve_subdivide.cc b/source/blender/nodes/geometry/nodes/node_geo_curve_subdivide.cc
index 3de2604cd0a..7908c26e2dc 100644
--- a/source/blender/nodes/geometry/nodes/node_geo_curve_subdivide.cc
+++ b/source/blender/nodes/geometry/nodes/node_geo_curve_subdivide.cc
@@ -116,38 +116,6 @@ static void subdivide_attribute(Span<T> src,
 }
 
 /**
- * De Casteljau Bezier subdivision.
- *
- * <pre>
- *           handle_prev         handle_next
- *                O----------------O
- *               /                  \
- *              /      x---O---x     \
- *             /         new_*        \
- *            /                        \
- *           O                          O
- *       point_prev                  point_next
- * </pre>
- */
-static void calculate_new_bezier_point(const float3 &point_prev,
-                                       float3 &handle_prev,
-                                       float3 &new_left_handle,
-                                       float3 &new_position,
-                                       float3 &new_right_handle,
-                                       float3 &handle_next,
-                                       const float3 &point_next,
-                                       const float parameter)
-{
-  const float3 center_point = float3::interpolate(handle_prev, handle_next, parameter);
-
-  handle_prev = float3::interpolate(point_prev, handle_prev, parameter);
-  handle_next = float3::interpolate(handle_next, point_next, parameter);
-  new_left_handle = float3::interpolate(handle_prev, center_point, parameter);
-  new_right_handle = float3::interpolate(center_point, handle_next, parameter);
-  new_position = float3::interpolate(new_left_handle, new_right_handle, parameter);
-}
-
-/**
  * 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.
@@ -171,6 +139,10 @@ static void subdivide_bezier_segment(const BezierSpline &src,
 {
   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;
@@ -178,7 +150,6 @@ static void subdivide_bezier_segment(const BezierSpline &src,
     dst_type_left.slice(offset + 1, result_size).fill(BezierSpline::HandleType::Vector);
     dst_type_right.slice(offset, result_size).fill(BezierSpline::HandleType::Vector);
 
-    dst_positions[offset] = src_positions[index];
     const float factor_delta = 1.0f / result_size;
     for (const int cut : IndexRange(result_size)) {
       const float factor = cut * factor_delta;
@@ -194,21 +165,38 @@ static void subdivide_bezier_segment(const BezierSpline &src,
     dst_type_right.slice(offset, result_size).fill(BezierSpline::HandleType::Free);
 
     const int i_segment_last = is_last_cyclic_segment ? 0 : offset + result_size;
-    dst_positions[offset] = src_positions[index];
-    dst_handles_right[offset] = src_handles_right[index];
-    dst_handles_left[i_segment_last] = src_handles_left[next_index];
+
+    /* 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);
-      calculate_new_bezier_point(dst_positions[offset + cut],
-                                 dst_handles_right[offset + cut],
-                                 dst_handles_left[offset + cut + 1],
-                                 dst_positions[offset + cut + 1],
-                                 dst_handles_right[offset + cut + 1],
-                                 dst_handles_left[i_segment_last],
-                                 src_positions[next_index],
-                                 parameter);
+      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;
   }
 }