Curves: Port subdivide node to the new data-block

This commit moves the subdivide curve node implementation to the
geometry module, changes it to work on the new curves data-block,
and adds support for Catmull Rom curves. Internally I also added
support for a curve domain selection. That isn't used, but it's
nice to have the option anyway.

Users should notice better performance as well, since we can avoid
many small allocations, and there is no conversion to and from the
old curve type.

The code uses a similar structure to the resample node (60a6fbf5b599)
and the set type node (9e393fc2f125). The resample curves node can be
restructured to be more similar to this soon though.

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

1 files changed, 74 insertions, 27 deletions

diff --git a/source/blender/blenkernel/intern/curve_catmull_rom.cc b/source/blender/blenkernel/intern/curve_catmull_rom.cc
index 1875c7b366a..952d59edcf9 100644
--- a/source/blender/blenkernel/intern/curve_catmull_rom.cc
+++ b/source/blender/blenkernel/intern/curve_catmull_rom.cc
@@ -39,15 +39,18 @@ static void evaluate_segment(const T &a, const T &b, const T &c, const T &d, Mut
   }
 }
 
-template<typename T>
+/**
+ * \param range_fn: Returns an index range describing where in the #dst span each segment should be
+ * evaluated to, and how many points to add to it. This is used to avoid the need to allocate an
+ * actual offsets array in typical evaluation use cases where the resolution is per-curve.
+ */
+template<typename T, typename RangeForSegmentFn>
 static void interpolate_to_evaluated(const Span<T> src,
                                      const bool cyclic,
-                                     const int resolution,
+                                     const RangeForSegmentFn &range_fn,
                                      MutableSpan<T> dst)
 
 {
-  BLI_assert(dst.size() == calculate_evaluated_num(src.size(), cyclic, resolution));
-
   /* - First deal with one and two point curves need special attention.
    * - Then evaluate the first and last segment(s) whose control points need to wrap around
    *   to the other side of the source array.
@@ -57,11 +60,14 @@ static void interpolate_to_evaluated(const Span<T> src,
     dst.first() = src.first();
     return;
   }
+
+  const IndexRange first = range_fn(0);
+
   if (src.size() == 2) {
-    evaluate_segment(src.first(), src.first(), src.last(), src.last(), dst.take_front(resolution));
+    evaluate_segment(src.first(), src.first(), src.last(), src.last(), dst.slice(first));
     if (cyclic) {
-      evaluate_segment(
-          src.last(), src.last(), src.first(), src.first(), dst.take_back(resolution));
+      const IndexRange last = range_fn(1);
+      evaluate_segment(src.last(), src.last(), src.first(), src.first(), dst.slice(last));
     }
     else {
       dst.last() = src.last();
@@ -69,39 +75,65 @@ static void interpolate_to_evaluated(const Span<T> src,
     return;
   }
 
+  const IndexRange second_to_last = range_fn(src.index_range().last(1));
+  const IndexRange last = range_fn(src.index_range().last());
   if (cyclic) {
-    /* The first segment. */
-    evaluate_segment(src.last(), src[0], src[1], src[2], dst.take_front(resolution));
-    /* The second-to-last segment. */
-    evaluate_segment(src.last(2),
-                     src.last(1),
-                     src.last(),
-                     src.first(),
-                     dst.take_back(resolution * 2).drop_back(resolution));
-    /* The last segment. */
-    evaluate_segment(src.last(1), src.last(), src[0], src[1], dst.take_back(resolution));
+    evaluate_segment(src.last(), src[0], src[1], src[2], dst.slice(first));
+    evaluate_segment(src.last(2), src.last(1), src.last(), src.first(), dst.slice(second_to_last));
+    evaluate_segment(src.last(1), src.last(), src[0], src[1], dst.slice(last));
   }
   else {
-    /* The first segment. */
-    evaluate_segment(src[0], src[0], src[1], src[2], dst.take_front(resolution));
-    /* The last segment. */
-    evaluate_segment(
-        src.last(2), src.last(1), src.last(), src.last(), dst.drop_back(1).take_back(resolution));
-    /* The final point of the last segment. */
+    evaluate_segment(src[0], src[0], src[1], src[2], dst.slice(first));
+    evaluate_segment(src.last(2), src.last(1), src.last(), src.last(), dst.slice(second_to_last));
+    /* For non-cyclic curves, the last segment should always just have a single point. We could
+     * assert that the size of the provided range is 1 here, but that would require specializing
+     * the #range_fn implementation for the last point, which may have a performance cost. */
     dst.last() = src.last();
   }
 
   /* Evaluate every segment that isn't the first or last. */
-  const int grain_size = std::max(512 / resolution, 1);
   const IndexRange inner_range = src.index_range().drop_back(2).drop_front(1);
-  threading::parallel_for(inner_range, grain_size, [&](IndexRange range) {
+  threading::parallel_for(inner_range, 512, [&](IndexRange range) {
     for (const int i : range) {
-      const IndexRange segment_range(resolution * i, resolution);
-      evaluate_segment(src[i - 1], src[i], src[i + 1], src[i + 2], dst.slice(segment_range));
+      const IndexRange segment = range_fn(i);
+      evaluate_segment(src[i - 1], src[i], src[i + 1], src[i + 2], dst.slice(segment));
     }
   });
 }
 
+template<typename T>
+static void interpolate_to_evaluated(const Span<T> src,
+                                     const bool cyclic,
+                                     const int resolution,
+                                     MutableSpan<T> dst)
+
+{
+  BLI_assert(dst.size() == calculate_evaluated_num(src.size(), cyclic, resolution));
+  interpolate_to_evaluated(
+      src,
+      cyclic,
+      [resolution](const int segment_i) -> IndexRange {
+        return {segment_i * resolution, resolution};
+      },
+      dst);
+}
+
+template<typename T>
+static void interpolate_to_evaluated(const Span<T> src,
+                                     const bool cyclic,
+                                     const Span<int> evaluated_offsets,
+                                     MutableSpan<T> dst)
+
+{
+  interpolate_to_evaluated(
+      src,
+      cyclic,
+      [evaluated_offsets](const int segment_i) -> IndexRange {
+        return bke::offsets_to_range(evaluated_offsets, segment_i);
+      },
+      dst);
+}
+
 void interpolate_to_evaluated(const GSpan src,
                               const bool cyclic,
                               const int resolution,
@@ -117,4 +149,19 @@ void interpolate_to_evaluated(const GSpan src,
   });
 }
 
+void interpolate_to_evaluated(const GSpan src,
+                              const bool cyclic,
+                              const Span<int> evaluated_offsets,
+                              GMutableSpan dst)
+{
+  attribute_math::convert_to_static_type(src.type(), [&](auto dummy) {
+    using T = decltype(dummy);
+    /* 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>) {
+      interpolate_to_evaluated(src.typed<T>(), cyclic, evaluated_offsets, dst.typed<T>());
+    }
+  });
+}
+
 }  // namespace blender::bke::curves::catmull_rom