Blender V5.3
sculpt_cut.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2026 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
5#include "sculpt_intern.hh"
6
7#include "BKE_brush.hh"
8#include "BKE_context.hh"
9#include "BKE_crazyspace.hh"
10#include "BKE_paint.hh"
11
12#include "ED_screen.hh"
13#include "ED_view3d.hh"
14
15#include "DEG_depsgraph.hh"
16
17#include "DNA_brush_types.h"
18
19#include "WM_api.hh"
20
21#include "BLI_array.hh"
22#include "BLI_array_utils.hh"
23#include "BLI_noise.hh"
24
25#include "GEO_trim_curves.hh"
26
28
29using bke::CurvesGeometry;
30
32 private:
34 CurvesBrush3D brush_3d_;
35
36 friend struct CutOperationExecutor;
37
38 public:
39 void on_stroke_extended(const PaintStroke &stroke,
40 const StrokeExtension &stroke_extension) override;
41};
42
44 float distance = std::numeric_limits<float>::max();
45 /*
46 * Which of the brush transforms caused the cut. Relevant for reverse projection with symmetry
47 * axes.
48 */
50};
51
57 CutOperation *self_ = nullptr;
59
60 Object *object_ = nullptr;
61 Curves *curves_id_ = nullptr;
63
67
69 const Brush *brush_ = nullptr;
74
76
77 CutOperationExecutor(const PaintStroke &stroke) : ctx_(stroke) {}
78
79 void execute(CutOperation &self, const StrokeExtension &stroke_extension)
80 {
81 self_ = &self;
83
84 curves_id_ = id_cast<Curves *>(object_->data);
85 curves_ = &curves_id_->geometry.wrap();
86 if (curves_->is_empty()) {
87 return;
88 }
89
92 return;
93 }
94
99 brush_pos_re_ = stroke_extension.mouse_position;
101
103 ".selection", bke::AttrDomain::Point, 1.0f);
105
106 const eBrushFalloffShape falloff_shape = brush_->falloff_shape;
107 if (stroke_extension.is_first) {
108 if (falloff_shape == PAINT_FALLOFF_SHAPE_SPHERE || (U.uiflag & USER_ORBIT_SELECTION)) {
109 self.brush_3d_ = *sample_curves_3d_brush(*ctx_.depsgraph,
110 *ctx_.region,
111 *ctx_.v3d,
112 *ctx_.rv3d,
113 *object_,
118 math::transform_point(transforms_.curves_to_world, self_->brush_3d_.position_cu));
119 }
120 }
121
122 const VArray<bool> cyclic = curves_->cyclic();
123 IndexMask curve_selection_without_cyclic = IndexMask::from_bools_inverse(
125 const bool selection_has_cyclic = curve_selection_without_cyclic.size() <
127 curve_selection_ = curve_selection_without_cyclic;
128
129 Array<BrushProjectionInfo> brush_projection_info(curves_->points_num());
130 if (falloff_shape == PAINT_FALLOFF_SHAPE_TUBE) {
131 this->find_projected_points_in_stroke_with_symmetry(brush_projection_info);
132 }
133 else if (falloff_shape == PAINT_FALLOFF_SHAPE_SPHERE) {
134 this->find_spherical_points_in_stroke_with_symmetry(brush_projection_info);
135 }
136 else {
138 }
139
140 Array<bool> curves_to_keep(curves_->curves_num(), true);
141 Array<float> ends(curves_->curves_num(), std::numeric_limits<float>::max());
142
143 this->cut_curves(brush_projection_info, curves_to_keep, ends);
144
145 IndexMaskMemory mask_memory;
146 const IndexMask mask_to_keep = IndexMask::from_bools(curves_to_keep, mask_memory);
147
148 *curves_ = bke::curves_copy_curve_selection(*curves_, mask_to_keep, {});
149
150 Array<float> kept_ends(mask_to_keep.size());
151 array_utils::gather(ends.as_span(), mask_to_keep, kept_ends.as_mutable_span());
152
153 if (!curves_->is_empty()) {
157 VArray<float>::from_span(kept_ends),
159 {});
160 }
161
162 if (selection_has_cyclic) {
163 report_cyclic_not_supported(stroke_extension.reports);
164 }
165
169 }
170
172 MutableSpan<BrushProjectionInfo> r_brush_projection_info)
173 {
174 const Vector<float4x4> symmetry_brush_transforms = get_symmetry_brush_transforms(
175 curves_id_->symmetry);
176 for (const int brush_transform_index : symmetry_brush_transforms.index_range()) {
177 const float4x4 &brush_transform = symmetry_brush_transforms[brush_transform_index];
179 math::invert(brush_transform), brush_transform_index, r_brush_projection_info);
180 }
181 }
182
183 void find_projected_points_in_stroke(const float4x4 &brush_transform_inv,
184 const int brush_transform_index,
185 MutableSpan<BrushProjectionInfo> r_brush_projection_info)
186 {
188
189 const bke::crazyspace::GeometryDeformation deformation =
191 const OffsetIndices points_by_curve = curves_->points_by_curve();
192
193 curve_selection_.foreach_index([&](const int curve_i) {
194 const IndexRange points = points_by_curve[curve_i];
195 for (const int i : IndexRange(points.size())) {
196 const int point_i = points[i];
197
198 const float3 &pos_cu = math::transform_point(brush_transform_inv,
199 deformation.positions[point_i]);
200 const float2 pos_re = ED_view3d_project_float_v2_m4(ctx_.region, pos_cu, projection);
201 const float dist_to_brush_sq_re = math::distance_squared(pos_re, brush_pos_re_);
202 if (dist_to_brush_sq_re < r_brush_projection_info[point_i].distance) {
203 r_brush_projection_info[point_i].distance = dist_to_brush_sq_re;
204 r_brush_projection_info[point_i].brush_transform_index = brush_transform_index;
205 }
206 }
207 });
208 }
209
211 MutableSpan<BrushProjectionInfo> r_brush_projection_info)
212 {
213 float3 brush_pos_wo;
215 ctx_.v3d,
216 ctx_.region,
219 brush_pos_wo);
220 const float3 brush_pos_cu = math::transform_point(transforms_.world_to_curves, brush_pos_wo);
221
222 const Vector<float4x4> symmetry_brush_transforms = get_symmetry_brush_transforms(
223 curves_id_->symmetry);
224 for (const int brush_transform_index : symmetry_brush_transforms.index_range()) {
225 const float4x4 &brush_transform = symmetry_brush_transforms[brush_transform_index];
226 this->find_spherical_points_in_stroke(brush_transform_index,
227 math::transform_point(brush_transform, brush_pos_cu),
228 r_brush_projection_info);
229 }
230 }
231
232 void find_spherical_points_in_stroke(const int brush_transform_index,
233 const float3 &brush_pos_cu,
234 MutableSpan<BrushProjectionInfo> r_brush_projection_info)
235 {
236 const bke::crazyspace::GeometryDeformation deformation =
238 const OffsetIndices points_by_curve = curves_->points_by_curve();
239
240 curve_selection_.foreach_index([&](const int curve_i) {
241 const IndexRange points = points_by_curve[curve_i];
242 for (const int i : IndexRange(points.size())) {
243 const int point_i = points[i];
244
245 const float3 &pos_cu = deformation.positions[point_i];
246 const float dist_to_brush_sq_cu = math::distance_squared(pos_cu, brush_pos_cu);
247 if (dist_to_brush_sq_cu < r_brush_projection_info[point_i].distance) {
248 r_brush_projection_info[point_i].distance = dist_to_brush_sq_cu;
249 r_brush_projection_info[point_i].brush_transform_index = brush_transform_index;
250 }
251 }
252 });
253 }
254
259 bool should_point_be_cut(const int point_i, const uint32_t stroke_hash)
260 {
261 if (point_factors_[point_i] <= 0.0f) {
262 return false;
263 }
264
265 if (brush_strength_ < 1.0f) {
266 const float stroke_chance = noise::hash_to_float(stroke_hash);
267 if (stroke_chance > brush_strength_) {
268 return false;
269 }
270 }
271
272 return true;
273 }
274
281 const float3 &point_inside_cu,
282 const float2 &brush_pos_re,
283 const float brush_radius_re,
284 const float4x4 &transform_cu_to_re)
285 {
286 const float2 point_outside_re = ED_view3d_project_float_v2_m4(
287 ctx_.region, point_outside_cu, transform_cu_to_re);
288 const float2 point_inside_re = ED_view3d_project_float_v2_m4(
289 ctx_.region, point_inside_cu, transform_cu_to_re);
290
291 /* Do the intersection in 2d space, but compute the intersection's position in 3d space. */
292 const float t = intersect_line_segment_sphere_2d(
293 point_outside_re, point_inside_re, brush_pos_re, brush_radius_re);
294
295 const float3 line_cu = point_inside_cu - point_outside_cu;
296 const float3 intersection_cu = point_outside_cu + t * line_cu;
297 return intersection_cu;
298 }
299
306 float intersect_line_segment_sphere_2d(const float2 &line_segment_start,
307 const float2 &line_segment_end,
308 const float2 &sphere_position,
309 const float sphere_radius)
310 {
311 const float2 line_re = line_segment_end - line_segment_start;
312 const float2 brush_to_outside_re = line_segment_start - sphere_position;
313
314 /* Solve a quadratic equation to find the line-segment-circle intersection. */
315 const float a = math::dot(line_re, line_re);
316 const float b = 2.0f * math::dot(line_re, brush_to_outside_re);
317 const float c = math::dot(brush_to_outside_re, brush_to_outside_re) -
318 sphere_radius * sphere_radius;
319
320 float d = b * b - 4.0f * a * c;
321 /* It shouldn't be possible to have no intersection (d < 0), so assume to be tangential. */
322 d = math::max(d, 0.0f);
323
324 const float t = (-b - sqrtf(d)) / (2.0f * a);
325 return t;
326 }
327
333 const float3 &point_inside_cu,
334 const float3 &brush_pos_cu,
335 const float brush_radius_cu)
336 {
337 const float3 line_cu = point_inside_cu - point_outside_cu;
338 const float3 brush_to_outside_cu = point_outside_cu - brush_pos_cu;
339
340 /* Solve a quadratic equation to find the line-segment-sphere intersection. */
341 const float a = math::dot(line_cu, line_cu);
342 const float b = 2.0f * math::dot(line_cu, brush_to_outside_cu);
343 const float c = math::dot(brush_to_outside_cu, brush_to_outside_cu) -
344 brush_radius_cu * brush_radius_cu;
345
346 float d = b * b - 4.0f * a * c;
347 /* It shouldn't be possible to have no intersection (d < 0), so assume to be tangential. */
348 d = math::max(d, 0.0f);
349
350 /* Compute the intersection point via the factor "t" along the line segment. */
351 const float t = (-b - sqrtf(d)) / (2.0f * a);
352
353 const float3 intersection_cu = point_outside_cu + t * line_cu;
354 return intersection_cu;
355 }
356
357 void cut_curves(const Span<BrushProjectionInfo> brush_projection_info,
358 MutableSpan<bool> r_curves_to_keep,
359 MutableSpan<float> r_ends)
360 {
361 const OffsetIndices points_by_curve = curves_->points_by_curve();
362 const Span<float3> positions = curves_->positions();
363
364 Array<float> segment_lengths(curves_->points_num());
366 [&](const IndexMaskSegment segment) {
367 for (const int curve_i : segment) {
368 const IndexRange points = points_by_curve[curve_i];
369 float accumulated_length = 0.0f;
370 for (const int i : points.index_range()) {
371 const int point_i = points[i];
372 if (i == 0) {
373 segment_lengths[point_i] = 0.0f;
374 continue;
375 }
376 const float3 &p1 = positions[point_i - 1];
377 const float3 &p2 = positions[point_i];
378 accumulated_length += math::distance(p1, p2);
379 segment_lengths[point_i] = accumulated_length;
380 }
381 }
382 },
384
385 const bke::crazyspace::GeometryDeformation deformation =
388
390 float brush_radius;
392 float3 brush_pos_cu;
393
394 const eBrushFalloffShape falloff_shape = brush_->falloff_shape;
395 switch (falloff_shape) {
398 break;
399 }
401 brush_radius = self_->brush_3d_.radius_cu * brush_radius_factor_;
402
403 float3 brush_pos_wo;
405 ctx_.v3d,
406 ctx_.region,
409 brush_pos_wo);
410 brush_pos_cu = math::transform_point(transforms_.world_to_curves, brush_pos_wo);
411 break;
412 }
413 }
414
415 const float brush_radius_sq = pow2f(brush_radius);
416 const uint64_t brush_pos_hash = brush_pos_re_.hash();
417 const Vector<float4x4> symmetry_brush_transforms = get_symmetry_brush_transforms(
418 curves_id_->symmetry);
419
421 [&](const int curve_i) {
422 const IndexRange points = points_by_curve[curve_i];
423 const Span<BrushProjectionInfo> brush_projection_info_slice =
424 brush_projection_info.slice(points);
425
426 const BrushProjectionInfo *first_point_in_stroke_bpi = std::find_if(
427 brush_projection_info_slice.begin(),
428 brush_projection_info_slice.end(),
429 [&](const BrushProjectionInfo projection_info) {
430 return projection_info.distance <= brush_radius_sq;
431 });
432 if (first_point_in_stroke_bpi == brush_projection_info_slice.end()) {
433 return;
434 }
435
436 const int first_point_in_stroke = std::distance(brush_projection_info_slice.begin(),
437 first_point_in_stroke_bpi);
438 const float4x4 brush_transform =
439 symmetry_brush_transforms[first_point_in_stroke_bpi->brush_transform_index];
440 const float4x4 brush_transform_inv = math::invert(brush_transform);
441
442 const uint32_t point_hash = noise::hash(
443 noise::hash_float(first_point_in_stroke_bpi->distance), brush_pos_hash);
444 const IndexRange::Iterator point_to_cut_iter = std::find_if(
445 points.begin(), points.end(), [&](const int point_i) {
446 const BrushProjectionInfo &bpi = brush_projection_info[point_i];
447 if (bpi.distance > brush_radius_sq) {
448 return false;
449 }
450 return should_point_be_cut(point_i, point_hash);
451 });
452 if (point_to_cut_iter == points.end()) {
453 return;
454 }
455 const int point_to_cut = std::distance(points.begin(), point_to_cut_iter);
456
457 if (point_to_cut == 0) {
458 /* Delete entire curve. Simply trimming would leave behind the root control point. */
459 r_curves_to_keep[curve_i] = false;
460 }
461 else if (first_point_in_stroke == point_to_cut) {
462 /* Brush boundary is cutting straight through previous and current point.
463 * Delete all points after current. */
464 const int current_point = points[point_to_cut];
465 const int previous_point = points[point_to_cut - 1];
466 const float3 &curr_pos_cu = deformation.positions[current_point];
467 const float3 &prev_pos_cu = deformation.positions[previous_point];
468 float3 boundary_cu;
469
470 if (falloff_shape == PAINT_FALLOFF_SHAPE_TUBE) {
471 boundary_cu = math::transform_point(
472 brush_transform,
474 math::transform_point(brush_transform_inv, prev_pos_cu),
475 math::transform_point(brush_transform_inv, curr_pos_cu),
477 brush_radius,
478 projection));
479 }
480 else if (falloff_shape == PAINT_FALLOFF_SHAPE_SPHERE) {
481 boundary_cu = find_spherical_cut_boundary(
482 prev_pos_cu,
483 curr_pos_cu,
484 math::transform_point(brush_transform_inv, brush_pos_cu),
485 brush_radius);
486 }
487 else {
489 }
490
491 const float boundary_length = math::distance(curr_pos_cu, boundary_cu);
492 r_ends[curve_i] = segment_lengths[current_point] - boundary_length;
493 }
494 else {
495 /* Brush is encompassing a boundary between selected and unselected points. */
496 const int previous_point = points[point_to_cut - 1];
497 r_ends[curve_i] = segment_lengths[previous_point];
498 }
499 },
501 }
502};
503
505 const StrokeExtension &stroke_extension)
506{
507 CutOperationExecutor executor{stroke};
508 executor.execute(*this, stroke_extension);
509}
510
511std::unique_ptr<CurvesSculptStrokeOperation> new_cut_operation()
512{
513 return std::make_unique<CutOperation>();
514}
515
516} // namespace blender::ed::sculpt_paint
#define NC_GEOM
Definition WM_types.hh:406
#define ND_DATA
Definition WM_types.hh:552
#define BLI_assert_unreachable()
Span< T > as_span() const
Definition BLI_array.hh:254
static IndexMask from_bools(Span< bool > bools, LinearAllocator<> &memory)
static IndexMask from_bools_inverse(Span< bool > bools, LinearAllocator<> &memory)
constexpr Iterator end() const
constexpr int64_t size() const
constexpr IndexRange()=default
constexpr Iterator begin() const
constexpr IndexRange index_range() const
constexpr Span slice(int64_t start, int64_t size) const
Definition BLI_span.hh:141
constexpr const T * end() const
Definition BLI_span.hh:228
constexpr const T * begin() const
Definition BLI_span.hh:224
static VArray from_single(T value, const int64_t size)
static VArray from_span(Span< T > values)
IndexRange index_range() const
GAttributeReader lookup_or_default(StringRef name, AttrDomain domain, AttrType data_type, const void *default_value=nullptr) const
VArray< bool > cyclic() const
AttributeAccessor attributes() const
Span< float3 > positions() const
OffsetIndices< int > points_by_curve() const
void on_stroke_extended(const PaintStroke &stroke, const StrokeExtension &stroke_extension) override
void foreach_segment(Fn &&fn, Mode mode=exec_mode::serial) const
void foreach_index(Fn &&fn, Mode mode=exec_mode::serial) const
float distance(float, float) RET
void gather(const GVArray &src, const IndexMask &indices, GMutableSpan dst, exec_mode::Mode mode=exec_mode::parallel)
GeometryDeformation get_evaluated_curves_deformation(const Object *ob_eval, const Object &ob_orig)
CurvesGeometry curves_copy_curve_selection(const CurvesGeometry &curves, const IndexMask &curves_to_copy, const AttributeFilter &attribute_filter)
IndexMask retrieve_selected_curves(const bke::CurvesGeometry &curves, LinearAllocator<> &memory)
void report_cyclic_not_supported(ReportList *reports)
float brush_strength_get(const Paint &paint, const Brush &brush, const StrokeExtension &stroke_extension)
std::optional< CurvesBrush3D > sample_curves_3d_brush(const Depsgraph &depsgraph, const ARegion &region, const View3D &v3d, const RegionView3D &rv3d, const Object &curves_object, const float2 &brush_pos_re, const float brush_radius_re)
void remember_stroke_position(CurvesSculpt &curves_sculpt, const float3 &brush_position_wo)
std::unique_ptr< CurvesSculptStrokeOperation > new_cut_operation()
Vector< float4x4 > get_symmetry_brush_transforms(const eCurvesSymmetryType symmetry)
float brush_radius_factor(const Brush &brush, const StrokeExtension &stroke_extension)
constexpr ParallelGrainSize grain_size(int grain_size)
bke::CurvesGeometry trim_curves(const bke::CurvesGeometry &src_curves, const IndexMask &selection, const VArray< float > &starts, const VArray< float > &ends, GeometryNodeCurveSampleMode mode, const bke::AttributeFilter &attribute_filter)
T distance(const T &a, const T &b)
T dot(const QuaternionBase< T > &a, const QuaternionBase< T > &b)
CartesianBasis invert(const CartesianBasis &basis)
T distance_squared(const VecBase< T, Size > &a, const VecBase< T, Size > &b)
T max(const T &a, const T &b)
VecBase< T, 3 > transform_point(const CartesianBasis &basis, const VecBase< T, 3 > &v)
uint32_t hash_float(float kx)
Definition noise.cc:200
uint32_t hash(uint32_t kx)
Definition noise.cc:89
float hash_to_float(uint32_t kx)
Definition noise.cc:232
void WM_main_add_notifier(uint type, void *reference)
UserDef U
Definition blender.cc:58
unsigned __int64 uint64_t
Definition BKE_text.h:91
float4x4 ED_view3d_ob_project_mat_get(const RegionView3D *rv3d, const Object *ob)
float BKE_brush_radius_get(const Paint *paint, const Brush *brush)
Definition brush.cc:1366
@ PAINT_FALLOFF_SHAPE_SPHERE
@ PAINT_FALLOFF_SHAPE_TUBE
float2 ED_view3d_project_float_v2_m4(const ARegion *region, const float co[3], const float4x4 &mat)
MatBase< float, 4, 4 > float4x4
void ED_region_tag_redraw(ARegion *region)
Definition area.cc:681
MINLINE float pow2f(float x)
unsigned int uint32_t
Definition BKE_text.h:81
VecBase< float, 2 > float2
void DEG_id_tag_update(ID *id, unsigned int flags)
const Brush * BKE_paint_brush_for_read(const Paint *paint)
@ ID_RECALC_GEOMETRY
Definition DNA_ID.h:1074
VecBase< float, 3 > float3
void ED_view3d_win_to_3d(const View3D *v3d, const ARegion *region, const float depth_pt[3], const float mval[2], float r_out[3])
@ GEO_NODE_CURVE_SAMPLE_LENGTH
#define sqrtf
eBrushFalloffShape falloff_shape
struct ToolSettings * toolsettings
CurvesSculpt * curves_sculpt
constexpr uint64_t hash() const
bool should_point_be_cut(const int point_i, const uint32_t stroke_hash)
void find_projected_points_in_stroke_with_symmetry(MutableSpan< BrushProjectionInfo > r_brush_projection_info)
CutOperationExecutor(const PaintStroke &stroke)
Definition sculpt_cut.cc:77
float3 find_projected_cut_boundary(const float3 &point_outside_cu, const float3 &point_inside_cu, const float2 &brush_pos_re, const float brush_radius_re, const float4x4 &transform_cu_to_re)
void find_spherical_points_in_stroke_with_symmetry(MutableSpan< BrushProjectionInfo > r_brush_projection_info)
float intersect_line_segment_sphere_2d(const float2 &line_segment_start, const float2 &line_segment_end, const float2 &sphere_position, const float sphere_radius)
void find_spherical_points_in_stroke(const int brush_transform_index, const float3 &brush_pos_cu, MutableSpan< BrushProjectionInfo > r_brush_projection_info)
void cut_curves(const Span< BrushProjectionInfo > brush_projection_info, MutableSpan< bool > r_curves_to_keep, MutableSpan< float > r_ends)
void find_projected_points_in_stroke(const float4x4 &brush_transform_inv, const int brush_transform_index, MutableSpan< BrushProjectionInfo > r_brush_projection_info)
void execute(CutOperation &self, const StrokeExtension &stroke_extension)
Definition sculpt_cut.cc:79
float3 find_spherical_cut_boundary(const float3 &point_outside_cu, const float3 &point_inside_cu, const float3 &brush_pos_cu, const float brush_radius_cu)