Curves: add initial comb, grow and shrink brush

The exact behavior of the brushes is still being iterated on, but it
helps having a base implementation that we can work upon.
All of that is still hidden behind an experimental feature flag anyway.

The brushes will get a name in the ui soon.

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

1 files changed, 316 insertions, 27 deletions

diff --git a/source/blender/editors/sculpt_paint/curves_sculpt_ops.cc b/source/blender/editors/sculpt_paint/curves_sculpt_ops.cc
index 12c03804981..4bf81b72c3c 100644
--- a/source/blender/editors/sculpt_paint/curves_sculpt_ops.cc
+++ b/source/blender/editors/sculpt_paint/curves_sculpt_ops.cc
@@ -11,6 +11,7 @@
 #include "BKE_mesh.h"
 #include "BKE_mesh_runtime.h"
 #include "BKE_paint.h"
+#include "BKE_spline.hh"
 
 #include "WM_api.h"
 #include "WM_toolsystem.h"
@@ -150,15 +151,22 @@ class DeleteOperation : public CurvesSculptStrokeOperation {
   }
 };
 
-class MoveOperation : public CurvesSculptStrokeOperation {
+/**
+ * Moves individual points under the brush and does a length preservation step afterwards.
+ */
+class CombOperation : public CurvesSculptStrokeOperation {
  private:
-  Vector<int64_t> points_to_move_indices_;
-  IndexMask points_to_move_;
   float2 last_mouse_position_;
 
  public:
   void on_stroke_extended(bContext *C, const StrokeExtension &stroke_extension) override
   {
+    BLI_SCOPED_DEFER([&]() { last_mouse_position_ = stroke_extension.mouse_position; });
+
+    if (stroke_extension.is_first) {
+      return;
+    }
+
     Scene &scene = *CTX_data_scene(C);
     Object &object = *CTX_data_active_object(C);
     ARegion *region = CTX_wm_region(C);
@@ -168,6 +176,10 @@ class MoveOperation : public CurvesSculptStrokeOperation {
     CurvesSculpt &curves_sculpt = *scene.toolsettings->curves_sculpt;
     Brush &brush = *BKE_paint_brush(&curves_sculpt.paint);
     const float brush_radius = BKE_brush_size_get(&scene, &brush);
+    const float brush_strength = BKE_brush_alpha_get(&scene, &brush);
+
+    const float4x4 ob_mat = object.obmat;
+    const float4x4 ob_imat = ob_mat.inverted();
 
     float4x4 projection;
     ED_view3d_ob_project_mat_get(rv3d, &object, projection.values);
@@ -176,39 +188,312 @@ class MoveOperation : public CurvesSculptStrokeOperation {
     CurvesGeometry &curves = CurvesGeometry::wrap(curves_id.geometry);
     MutableSpan<float3> positions = curves.positions();
 
-    if (stroke_extension.is_first) {
-      /* Find point indices to move. */
-      points_to_move_ = index_mask_ops::find_indices_based_on_predicate(
-          curves.points_range(), 512, points_to_move_indices_, [&](const int64_t point_i) {
-            const float3 position = positions[point_i];
-            float2 screen_position;
-            ED_view3d_project_float_v2_m4(region, position, screen_position, projection.values);
-            const float distance = len_v2v2(screen_position, stroke_extension.mouse_position);
-            return distance <= brush_radius;
-          });
-    }
-    else {
-      /* Move points based on mouse movement. */
-      const float2 mouse_diff = stroke_extension.mouse_position - last_mouse_position_;
-      threading::parallel_for(points_to_move_.index_range(), 512, [&](const IndexRange range) {
-        for (const int point_i : points_to_move_.slice(range)) {
+    const float2 mouse_prev = last_mouse_position_;
+    const float2 mouse_cur = stroke_extension.mouse_position;
+    const float2 mouse_diff = mouse_cur - mouse_prev;
+    const float mouse_diff_len = math::length(mouse_diff);
+
+    threading::parallel_for(curves.curves_range(), 256, [&](const IndexRange curves_range) {
+      for (const int curve_i : curves_range) {
+        const IndexRange curve_points = curves.range_for_curve(curve_i);
+        /* Compute lengths of the segments. Those are used to make sure that the lengths don't
+         * change. */
+        Vector<float, 16> segment_lengths(curve_points.size() - 1);
+        for (const int segment_i : IndexRange(curve_points.size() - 1)) {
+          const float3 &p1 = positions[curve_points[segment_i]];
+          const float3 &p2 = positions[curve_points[segment_i] + 1];
+          const float length = math::distance(p1, p2);
+          segment_lengths[segment_i] = length;
+        }
+        bool curve_changed = false;
+        for (const int point_i : curve_points.drop_front(1)) {
           const float3 old_position = positions[point_i];
+
+          /* Find the position of the point in screen space. */
           float2 old_position_screen;
           ED_view3d_project_float_v2_m4(
               region, old_position, old_position_screen, projection.values);
-          const float2 new_position_screen = old_position_screen + mouse_diff;
+
+          /* Project the point onto the line drawn by the mouse. Note, it's projected on the
+           * infinite line, not only on the line segment. */
+          float2 old_position_screen_proj;
+          /* t is 0 when the point is closest to the previous mouse position and 1 when it's
+           * closest to the current mouse position. */
+          const float t = closest_to_line_v2(
+              old_position_screen_proj, old_position_screen, mouse_prev, mouse_cur);
+
+          /* Compute the distance to the mouse line segment. */
+          const float2 old_position_screen_proj_segment = mouse_prev +
+                                                          std::clamp(t, 0.0f, 1.0f) * mouse_diff;
+          const float distance_screen = math::distance(old_position_screen,
+                                                       old_position_screen_proj_segment);
+          if (distance_screen > brush_radius) {
+            /* Ignore the point because it's too far away. */
+            continue;
+          }
+          /* Compute a falloff that is based on how far along the point along the last stroke
+           * segment is. */
+          const float t_overshoot = brush_radius / mouse_diff_len;
+          const float t_falloff = 1.0f - std::max(t, 0.0f) / (1.0f + t_overshoot);
+          /* A falloff that is based on how far away the point is from the stroke. */
+          const float radius_falloff = pow2f(1.0f - distance_screen / brush_radius);
+          /* Combine the different falloffs and brush strength. */
+          const float weight = brush_strength * t_falloff * radius_falloff;
+
+          /* Offset the old point position in screen space and transform it back into 3D space. */
+          const float2 new_position_screen = old_position_screen + mouse_diff * weight;
           float3 new_position;
-          ED_view3d_win_to_3d(v3d, region, old_position, new_position_screen, new_position);
+          ED_view3d_win_to_3d(
+              v3d, region, ob_mat * old_position, new_position_screen, new_position);
+          new_position = ob_imat * new_position;
           positions[point_i] = new_position;
+
+          curve_changed = true;
         }
-      });
+        if (!curve_changed) {
+          continue;
+        }
+        /* Ensure that the length of each segment stays the same. */
+        for (const int segment_i : IndexRange(curve_points.size() - 1)) {
+          const float3 &p1 = positions[curve_points[segment_i]];
+          float3 &p2 = positions[curve_points[segment_i] + 1];
+          const float3 direction = math::normalize(p2 - p1);
+          const float desired_length = segment_lengths[segment_i];
+          p2 = p1 + direction * desired_length;
+        }
+      }
+    });
 
-      curves.tag_positions_changed();
-      DEG_id_tag_update(&curves_id.id, ID_RECALC_GEOMETRY);
-      ED_region_tag_redraw(region);
+    curves.tag_positions_changed();
+    DEG_id_tag_update(&curves_id.id, ID_RECALC_GEOMETRY);
+    ED_region_tag_redraw(region);
+  }
+};
+
+/**
+ * Drags the tip point of each curve and resamples the rest of the curve.
+ */
+class GrowOperation : public CurvesSculptStrokeOperation {
+ private:
+  float2 last_mouse_position_;
+
+ public:
+  void on_stroke_extended(bContext *C, const StrokeExtension &stroke_extension) override
+  {
+    BLI_SCOPED_DEFER([&]() { last_mouse_position_ = stroke_extension.mouse_position; });
+
+    if (stroke_extension.is_first) {
+      return;
     }
 
-    last_mouse_position_ = stroke_extension.mouse_position;
+    Scene &scene = *CTX_data_scene(C);
+    Object &object = *CTX_data_active_object(C);
+    ARegion *region = CTX_wm_region(C);
+    View3D *v3d = CTX_wm_view3d(C);
+    RegionView3D *rv3d = CTX_wm_region_view3d(C);
+
+    CurvesSculpt &curves_sculpt = *scene.toolsettings->curves_sculpt;
+    Brush &brush = *BKE_paint_brush(&curves_sculpt.paint);
+    const float brush_radius = BKE_brush_size_get(&scene, &brush);
+    const float brush_strength = BKE_brush_alpha_get(&scene, &brush);
+
+    const float4x4 ob_mat = object.obmat;
+    const float4x4 ob_imat = ob_mat.inverted();
+
+    float4x4 projection;
+    ED_view3d_ob_project_mat_get(rv3d, &object, projection.values);
+
+    Curves &curves_id = *static_cast<Curves *>(object.data);
+    CurvesGeometry &curves = CurvesGeometry::wrap(curves_id.geometry);
+    MutableSpan<float3> positions = curves.positions();
+
+    const float2 mouse_prev = last_mouse_position_;
+    const float2 mouse_cur = stroke_extension.mouse_position;
+    const float2 mouse_diff = mouse_cur - mouse_prev;
+
+    threading::parallel_for(curves.curves_range(), 256, [&](const IndexRange curves_range) {
+      for (const int curve_i : curves_range) {
+        const IndexRange curve_points = curves.range_for_curve(curve_i);
+        const int last_point_i = curve_points.last();
+
+        const float3 old_position = positions[last_point_i];
+
+        float2 old_position_screen;
+        ED_view3d_project_float_v2_m4(
+            region, old_position, old_position_screen, projection.values);
+
+        const float distance_screen = math::distance(old_position_screen, mouse_prev);
+        if (distance_screen > brush_radius) {
+          continue;
+        }
+
+        const float radius_falloff = pow2f(1.0f - distance_screen / brush_radius);
+        const float weight = brush_strength * radius_falloff;
+
+        const float2 new_position_screen = old_position_screen + mouse_diff * weight;
+        float3 new_position;
+        ED_view3d_win_to_3d(v3d, region, ob_mat * old_position, new_position_screen, new_position);
+        new_position = ob_imat * new_position;
+
+        this->move_last_point_and_resample(positions, curve_points, new_position);
+      }
+    });
+
+    curves.tag_positions_changed();
+    DEG_id_tag_update(&curves_id.id, ID_RECALC_GEOMETRY);
+    ED_region_tag_redraw(region);
+  }
+
+  void move_last_point_and_resample(MutableSpan<float3> positions,
+                                    const IndexRange curve_points,
+                                    const float3 &new_last_point_position) const
+  {
+    Vector<float> old_lengths;
+    old_lengths.append(0.0f);
+    /* Used to (1) normalize the segment sizes over time and (2) support making zero-length
+     * segments */
+    const float extra_length = 0.001f;
+    for (const int segment_i : IndexRange(curve_points.size() - 1)) {
+      const float3 &p1 = positions[curve_points[segment_i]];
+      const float3 &p2 = positions[curve_points[segment_i] + 1];
+      const float length = math::distance(p1, p2);
+      old_lengths.append(old_lengths.last() + length + extra_length);
+    }
+    Vector<float> point_factors;
+    for (float &old_length : old_lengths) {
+      point_factors.append(old_length / old_lengths.last());
+    }
+
+    PolySpline new_spline;
+    new_spline.resize(curve_points.size());
+    MutableSpan<float3> new_spline_positions = new_spline.positions();
+    for (const int i : IndexRange(curve_points.size() - 1)) {
+      new_spline_positions[i] = positions[curve_points[i]];
+    }
+    new_spline_positions.last() = new_last_point_position;
+    new_spline.mark_cache_invalid();
+
+    for (const int i : IndexRange(curve_points.size())) {
+      const float factor = point_factors[i];
+      const Spline::LookupResult lookup = new_spline.lookup_evaluated_factor(factor);
+      const float index_factor = lookup.evaluated_index + lookup.factor;
+      float3 p;
+      new_spline.sample_with_index_factors<float3>(
+          new_spline_positions, {&index_factor, 1}, {&p, 1});
+      positions[curve_points[i]] = p;
+    }
+  }
+};
+
+/**
+ * Resamples the curves to a shorter length.
+ */
+class ShrinkOperation : public CurvesSculptStrokeOperation {
+ private:
+  float2 last_mouse_position_;
+
+ public:
+  void on_stroke_extended(bContext *C, const StrokeExtension &stroke_extension) override
+  {
+    BLI_SCOPED_DEFER([&]() { last_mouse_position_ = stroke_extension.mouse_position; });
+
+    if (stroke_extension.is_first) {
+      return;
+    }
+
+    Scene &scene = *CTX_data_scene(C);
+    Object &object = *CTX_data_active_object(C);
+    ARegion *region = CTX_wm_region(C);
+    View3D *v3d = CTX_wm_view3d(C);
+    RegionView3D *rv3d = CTX_wm_region_view3d(C);
+
+    CurvesSculpt &curves_sculpt = *scene.toolsettings->curves_sculpt;
+    Brush &brush = *BKE_paint_brush(&curves_sculpt.paint);
+    const float brush_radius = BKE_brush_size_get(&scene, &brush);
+    const float brush_strength = BKE_brush_alpha_get(&scene, &brush);
+
+    const float4x4 ob_mat = object.obmat;
+    const float4x4 ob_imat = ob_mat.inverted();
+
+    float4x4 projection;
+    ED_view3d_ob_project_mat_get(rv3d, &object, projection.values);
+
+    Curves &curves_id = *static_cast<Curves *>(object.data);
+    CurvesGeometry &curves = CurvesGeometry::wrap(curves_id.geometry);
+    MutableSpan<float3> positions = curves.positions();
+
+    const float2 mouse_prev = last_mouse_position_;
+    const float2 mouse_cur = stroke_extension.mouse_position;
+    const float2 mouse_diff = mouse_cur - mouse_prev;
+
+    threading::parallel_for(curves.curves_range(), 256, [&](const IndexRange curves_range) {
+      for (const int curve_i : curves_range) {
+        const IndexRange curve_points = curves.range_for_curve(curve_i);
+        const int last_point_i = curve_points.last();
+
+        const float3 old_tip_position = positions[last_point_i];
+
+        float2 old_tip_position_screen;
+        ED_view3d_project_float_v2_m4(
+            region, old_tip_position, old_tip_position_screen, projection.values);
+
+        const float distance_screen = math::distance(old_tip_position_screen, mouse_prev);
+        if (distance_screen > brush_radius) {
+          continue;
+        }
+
+        const float radius_falloff = pow2f(1.0f - distance_screen / brush_radius);
+        const float weight = brush_strength * radius_falloff;
+
+        const float2 offset_tip_position_screen = old_tip_position_screen + weight * mouse_diff;
+        float3 offset_tip_position;
+        ED_view3d_win_to_3d(v3d,
+                            region,
+                            ob_mat * old_tip_position,
+                            offset_tip_position_screen,
+                            offset_tip_position);
+        offset_tip_position = ob_imat * offset_tip_position;
+        const float shrink_length = math::distance(offset_tip_position, old_tip_position);
+
+        this->shrink_curve(positions, curve_points, shrink_length);
+      }
+    });
+
+    curves.tag_positions_changed();
+    DEG_id_tag_update(&curves_id.id, ID_RECALC_GEOMETRY);
+    ED_region_tag_redraw(region);
+  }
+
+  void shrink_curve(MutableSpan<float3> positions,
+                    const IndexRange curve_points,
+                    const float shrink_length) const
+  {
+    PolySpline spline;
+    spline.resize(curve_points.size());
+    MutableSpan<float3> spline_positions = spline.positions();
+    spline_positions.copy_from(positions.slice(curve_points));
+    spline.mark_cache_invalid();
+    const float old_length = spline.length();
+    const float new_length = std::max(0.0f, old_length - shrink_length);
+    const float length_factor = new_length / old_length;
+
+    Vector<float> old_point_lengths;
+    old_point_lengths.append(0.0f);
+    for (const int i : spline_positions.index_range().drop_back(1)) {
+      const float3 &p1 = spline_positions[i];
+      const float3 &p2 = spline_positions[i + 1];
+      const float length = math::distance(p1, p2);
+      old_point_lengths.append(old_point_lengths.last() + length);
+    }
+
+    for (const int i : spline_positions.index_range()) {
+      const float eval_length = old_point_lengths[i] * length_factor;
+      const Spline::LookupResult lookup = spline.lookup_evaluated_length(eval_length);
+      const float index_factor = lookup.evaluated_index + lookup.factor;
+      float3 p;
+      spline.sample_with_index_factors<float3>(spline_positions, {&index_factor, 1}, {&p, 1});
+      positions[curve_points[i]] = p;
+    }
   }
 };
 
@@ -652,11 +937,15 @@ static std::unique_ptr<CurvesSculptStrokeOperation> start_brush_operation(bConte
   Brush &brush = *BKE_paint_brush(&curves_sculpt.paint);
   switch (brush.curves_sculpt_tool) {
     case CURVES_SCULPT_TOOL_TEST1:
-      return std::make_unique<MoveOperation>();
+      return std::make_unique<CombOperation>();
     case CURVES_SCULPT_TOOL_TEST2:
       return std::make_unique<DeleteOperation>();
     case CURVES_SCULPT_TOOL_TEST3:
       return std::make_unique<AddOperation>();
+    case CURVES_SCULPT_TOOL_TEST4:
+      return std::make_unique<GrowOperation>();
+    case CURVES_SCULPT_TOOL_TEST5:
+      return std::make_unique<ShrinkOperation>();
   }
   BLI_assert_unreachable();
   return {};