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.

1 files changed, 32 insertions, 44 deletions

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