diff options
-rw-r--r-- | source/blender/blenkernel/BKE_curves.hh | 1 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/curves_geometry.cc | 191 | ||||
-rw-r--r-- | source/blender/nodes/geometry/nodes/node_geo_delete_geometry.cc | 175 |
3 files changed, 201 insertions, 166 deletions
diff --git a/source/blender/blenkernel/BKE_curves.hh b/source/blender/blenkernel/BKE_curves.hh index 28d03f96db1..2bebd3ff97d 100644 --- a/source/blender/blenkernel/BKE_curves.hh +++ b/source/blender/blenkernel/BKE_curves.hh @@ -387,6 +387,7 @@ class CurvesGeometry : public ::CurvesGeometry { void update_customdata_pointers(); + void remove_points(IndexMask points_to_delete); void remove_curves(IndexMask curves_to_delete); /** diff --git a/source/blender/blenkernel/intern/curves_geometry.cc b/source/blender/blenkernel/intern/curves_geometry.cc index 3c060bd1b8f..1c3715aaf69 100644 --- a/source/blender/blenkernel/intern/curves_geometry.cc +++ b/source/blender/blenkernel/intern/curves_geometry.cc @@ -1100,6 +1100,165 @@ static void *ensure_customdata_layer(CustomData &custom_data, &custom_data, data_type, CD_DEFAULT, nullptr, tot_elements, name.c_str()); } +static void copy_between_buffers(const CPPType &type, + const void *src_buffer, + void *dst_buffer, + const IndexRange src_range, + const IndexRange dst_range) +{ + BLI_assert(src_range.size() == dst_range.size()); + type.copy_construct_n(POINTER_OFFSET(src_buffer, type.size() * src_range.start()), + POINTER_OFFSET(dst_buffer, type.size() * dst_range.start()), + src_range.size()); +} + +template<typename T> +static void copy_with_map(const Span<T> src, const Span<int> map, MutableSpan<T> dst) +{ + threading::parallel_for(map.index_range(), 1024, [&](const IndexRange range) { + for (const int i : range) { + dst[i] = src[map[i]]; + } + }); +} + +static void copy_with_map(const GSpan src, const Span<int> map, GMutableSpan dst) +{ + attribute_math::convert_to_static_type(src.type(), [&](auto dummy) { + using T = decltype(dummy); + copy_with_map(src.typed<T>(), map, dst.typed<T>()); + }); +} + +/** + * Builds an array that for every point, contains the corresponding curve index. + */ +static Array<int> build_point_to_curve_map(const CurvesGeometry &curves) +{ + Array<int> point_to_curve_map(curves.points_num()); + threading::parallel_for(curves.curves_range(), 1024, [&](const IndexRange curves_range) { + for (const int i_curve : curves_range) { + point_to_curve_map.as_mutable_span().slice(curves.points_for_curve(i_curve)).fill(i_curve); + } + }); + return point_to_curve_map; +} + +static CurvesGeometry copy_with_removed_points(const CurvesGeometry &curves, + const IndexMask points_to_delete) +{ + /* Use a map from points to curves to facilitate using an #IndexMask input. */ + const Array<int> point_to_curve_map = build_point_to_curve_map(curves); + + const Vector<IndexRange> copy_point_ranges = points_to_delete.extract_ranges_invert( + curves.points_range()); + + /* For every range of points to copy, find the offset in the result curves point layers. */ + int new_point_count = 0; + Array<int> copy_point_range_dst_offsets(copy_point_ranges.size()); + for (const int i : copy_point_ranges.index_range()) { + copy_point_range_dst_offsets[i] = new_point_count; + new_point_count += copy_point_ranges[i].size(); + } + BLI_assert(new_point_count == (curves.points_num() - points_to_delete.size())); + + /* Find out how many non-deleted points there are in every curve. */ + Array<int> curve_point_counts(curves.curves_num(), 0); + for (const IndexRange range : copy_point_ranges) { + for (const int point_i : range) { + curve_point_counts[point_to_curve_map[point_i]]++; + } + } + + /* Build the offsets for the new curve points, skipping curves that had all points deleted. + * Also store the original indices of the corresponding input curves, to facilitate parallel + * copying of curve domain data. */ + int new_curve_count = 0; + int curve_point_offset = 0; + Vector<int> new_curve_offsets; + Vector<int> new_curve_orig_indices; + new_curve_offsets.append(0); + for (const int i : curve_point_counts.index_range()) { + if (curve_point_counts[i] > 0) { + curve_point_offset += curve_point_counts[i]; + new_curve_offsets.append(curve_point_offset); + + new_curve_count++; + new_curve_orig_indices.append(i); + } + } + + CurvesGeometry new_curves{new_point_count, new_curve_count}; + + threading::parallel_invoke( + /* Initialize curve offsets. */ + [&]() { new_curves.offsets_for_write().copy_from(new_curve_offsets); }, + /* Copy over point attributes. */ + [&]() { + const CustomData &old_point_data = curves.point_data; + CustomData &new_point_data = new_curves.point_data; + for (const int layer_i : IndexRange(old_point_data.totlayer)) { + const CustomDataLayer &old_layer = old_point_data.layers[layer_i]; + const eCustomDataType data_type = static_cast<eCustomDataType>(old_layer.type); + const CPPType &type = *bke::custom_data_type_to_cpp_type(data_type); + + void *dst_buffer = ensure_customdata_layer( + new_point_data, old_layer.name, data_type, new_point_count); + + threading::parallel_for( + copy_point_ranges.index_range(), 128, [&](const IndexRange ranges_range) { + for (const int range_i : ranges_range) { + const IndexRange src_range = copy_point_ranges[range_i]; + copy_between_buffers(type, + old_layer.data, + dst_buffer, + src_range, + {copy_point_range_dst_offsets[range_i], src_range.size()}); + } + }); + } + }, + /* Copy over curve attributes. + * In some cases points are just dissolved, so the the number of + * curves will be the same. That could be optimized in the future. */ + [&]() { + const CustomData &old_curve_data = curves.curve_data; + CustomData &new_curve_data = new_curves.curve_data; + for (const int layer_i : IndexRange(old_curve_data.totlayer)) { + const CustomDataLayer &old_layer = old_curve_data.layers[layer_i]; + const eCustomDataType data_type = static_cast<eCustomDataType>(old_layer.type); + const CPPType &type = *bke::custom_data_type_to_cpp_type(data_type); + + void *dst_buffer = ensure_customdata_layer( + new_curve_data, old_layer.name, data_type, new_curve_count); + + if (new_curves.curves_num() == curves.curves_num()) { + type.copy_construct_n(old_layer.data, dst_buffer, new_curves.curves_num()); + } + else { + copy_with_map({type, old_layer.data, curves.curves_num()}, + new_curve_orig_indices, + {type, dst_buffer, new_curves.curves_num()}); + } + } + }); + + new_curves.update_curve_types(); + + return new_curves; +} + +void CurvesGeometry::remove_points(const IndexMask points_to_delete) +{ + if (points_to_delete.is_empty()) { + return; + } + if (points_to_delete.size() == this->points_num()) { + *this = {}; + } + *this = copy_with_removed_points(*this, points_to_delete); +} + static CurvesGeometry copy_with_removed_curves(const CurvesGeometry &curves, const IndexMask curves_to_delete) { @@ -1159,20 +1318,17 @@ static CurvesGeometry copy_with_removed_curves(const CurvesGeometry &curves, const eCustomDataType data_type = static_cast<eCustomDataType>(old_layer.type); const CPPType &type = *bke::custom_data_type_to_cpp_type(data_type); - const void *src_buffer = old_layer.data; void *dst_buffer = ensure_customdata_layer( new_point_data, old_layer.name, data_type, new_tot_points); threading::parallel_for( old_curve_ranges.index_range(), 128, [&](const IndexRange ranges_range) { for (const int range_i : ranges_range) { - const IndexRange old_point_range = old_point_ranges[range_i]; - const IndexRange new_point_range = new_point_ranges[range_i]; - - type.copy_construct_n( - POINTER_OFFSET(src_buffer, type.size() * old_point_range.start()), - POINTER_OFFSET(dst_buffer, type.size() * new_point_range.start()), - old_point_range.size()); + copy_between_buffers(type, + old_layer.data, + dst_buffer, + old_point_ranges[range_i], + new_point_ranges[range_i]); } }); } @@ -1186,20 +1342,17 @@ static CurvesGeometry copy_with_removed_curves(const CurvesGeometry &curves, const eCustomDataType data_type = static_cast<eCustomDataType>(old_layer.type); const CPPType &type = *bke::custom_data_type_to_cpp_type(data_type); - const void *src_buffer = old_layer.data; void *dst_buffer = ensure_customdata_layer( new_curve_data, old_layer.name, data_type, new_tot_curves); threading::parallel_for( old_curve_ranges.index_range(), 128, [&](const IndexRange ranges_range) { for (const int range_i : ranges_range) { - const IndexRange old_curve_range = old_curve_ranges[range_i]; - const IndexRange new_curve_range = new_curve_ranges[range_i]; - - type.copy_construct_n( - POINTER_OFFSET(src_buffer, type.size() * old_curve_range.start()), - POINTER_OFFSET(dst_buffer, type.size() * new_curve_range.start()), - old_curve_range.size()); + copy_between_buffers(type, + old_layer.data, + dst_buffer, + old_curve_ranges[range_i], + new_curve_ranges[range_i]); } }); } @@ -1212,6 +1365,12 @@ static CurvesGeometry copy_with_removed_curves(const CurvesGeometry &curves, void CurvesGeometry::remove_curves(const IndexMask curves_to_delete) { + if (curves_to_delete.is_empty()) { + return; + } + if (curves_to_delete.size() == this->curves_num()) { + *this = {}; + } *this = copy_with_removed_curves(*this, curves_to_delete); } diff --git a/source/blender/nodes/geometry/nodes/node_geo_delete_geometry.cc b/source/blender/nodes/geometry/nodes/node_geo_delete_geometry.cc index fba696b5b95..08b107e0152 100644 --- a/source/blender/nodes/geometry/nodes/node_geo_delete_geometry.cc +++ b/source/blender/nodes/geometry/nodes/node_geo_delete_geometry.cc @@ -8,10 +8,10 @@ #include "DNA_mesh_types.h" #include "DNA_meshdata_types.h" +#include "BKE_curves.hh" #include "BKE_customdata.h" #include "BKE_mesh.h" #include "BKE_pointcloud.h" -#include "BKE_spline.hh" #include "node_geometry_util.hh" @@ -311,161 +311,35 @@ static void copy_masked_polys_to_new_mesh(const Mesh &src_mesh, } } -static void spline_copy_builtin_attributes(const Spline &spline, - Spline &r_spline, - const IndexMask mask) -{ - copy_data_based_on_mask(spline.positions(), r_spline.positions(), mask); - copy_data_based_on_mask(spline.radii(), r_spline.radii(), mask); - copy_data_based_on_mask(spline.tilts(), r_spline.tilts(), mask); - switch (spline.type()) { - case CURVE_TYPE_POLY: - break; - case CURVE_TYPE_BEZIER: { - const BezierSpline &src = static_cast<const BezierSpline &>(spline); - BezierSpline &dst = static_cast<BezierSpline &>(r_spline); - copy_data_based_on_mask(src.handle_positions_left(), dst.handle_positions_left(), mask); - copy_data_based_on_mask(src.handle_positions_right(), dst.handle_positions_right(), mask); - copy_data_based_on_mask(src.handle_types_left(), dst.handle_types_left(), mask); - copy_data_based_on_mask(src.handle_types_right(), dst.handle_types_right(), mask); - break; - } - case CURVE_TYPE_NURBS: { - const NURBSpline &src = static_cast<const NURBSpline &>(spline); - NURBSpline &dst = static_cast<NURBSpline &>(r_spline); - copy_data_based_on_mask(src.weights(), dst.weights(), mask); - break; - } - case CURVE_TYPE_CATMULL_ROM: { - BLI_assert_unreachable(); - break; - } - } -} - -static void copy_dynamic_attributes(const CustomDataAttributes &src, - CustomDataAttributes &dst, - const IndexMask mask) -{ - src.foreach_attribute( - [&](const AttributeIDRef &attribute_id, const AttributeMetaData &meta_data) { - std::optional<GSpan> src_attribute = src.get_for_read(attribute_id); - BLI_assert(src_attribute); - - if (!dst.create(attribute_id, meta_data.data_type)) { - /* Since the source spline of the same type had the attribute, adding it should work. - */ - BLI_assert_unreachable(); - } - - std::optional<GMutableSpan> new_attribute = dst.get_for_write(attribute_id); - BLI_assert(new_attribute); - - attribute_math::convert_to_static_type(new_attribute->type(), [&](auto dummy) { - using T = decltype(dummy); - copy_data_based_on_mask(src_attribute->typed<T>(), new_attribute->typed<T>(), mask); - }); - return true; - }, - ATTR_DOMAIN_POINT); -} - -/** - * Deletes points in the spline. Those not in the mask are deleted. The spline is not split into - * multiple newer splines. - */ -static SplinePtr spline_delete(const Spline &spline, const IndexMask mask) -{ - SplinePtr new_spline = spline.copy_only_settings(); - new_spline->resize(mask.size()); - - spline_copy_builtin_attributes(spline, *new_spline, mask); - copy_dynamic_attributes(spline.attributes, new_spline->attributes, mask); - - return new_spline; -} - -static std::unique_ptr<CurveEval> curve_separate(const CurveEval &input_curve, - const Span<bool> selection, - const eAttrDomain selection_domain) +static void delete_curves_selection(GeometrySet &geometry_set, + const Field<bool> &selection_field, + const eAttrDomain selection_domain) { - Span<SplinePtr> input_splines = input_curve.splines(); - std::unique_ptr<CurveEval> output_curve = std::make_unique<CurveEval>(); - - /* Keep track of which splines were copied to the result to copy spline domain attributes. */ - Vector<int64_t> copied_splines; - - if (selection_domain == ATTR_DOMAIN_CURVE) { - /* Operates on each of the splines as a whole, i.e. not on the points in the splines - * themselves. */ - for (const int i : selection.index_range()) { - if (selection[i]) { - output_curve->add_spline(input_splines[i]->copy()); - copied_splines.append(i); - } - } - } - else { - /* Operates on the points in the splines themselves. */ - - /* Reuse index vector for each spline. */ - Vector<int64_t> indices_to_copy; - - int selection_index = 0; - for (const int i : input_splines.index_range()) { - const Spline &spline = *input_splines[i]; - - indices_to_copy.clear(); - for (const int i_point : IndexRange(spline.size())) { - if (selection[selection_index]) { - /* Append i_point instead of selection_index because we need indices local to the spline - * for copying. */ - indices_to_copy.append(i_point); - } - selection_index++; - } - - /* Avoid creating an empty spline. */ - if (indices_to_copy.is_empty()) { - continue; - } + const CurveComponent &src_component = *geometry_set.get_component_for_read<CurveComponent>(); + GeometryComponentFieldContext field_context{src_component, selection_domain}; - SplinePtr new_spline = spline_delete(spline, IndexMask(indices_to_copy)); - output_curve->add_spline(std::move(new_spline)); - copied_splines.append(i); - } + const int domain_num = src_component.attribute_domain_num(selection_domain); + fn::FieldEvaluator evaluator{field_context, domain_num}; + evaluator.set_selection(selection_field); + evaluator.evaluate(); + const IndexMask selection = evaluator.get_evaluated_selection_as_mask(); + if (selection.is_empty()) { + return; } - - if (copied_splines.is_empty()) { - return {}; + if (selection.size() == domain_num) { + geometry_set.remove<CurveComponent>(); + return; } - output_curve->attributes.reallocate(output_curve->splines().size()); - copy_dynamic_attributes( - input_curve.attributes, output_curve->attributes, IndexMask(copied_splines)); - - return output_curve; -} - -static void separate_curve_selection(GeometrySet &geometry_set, - const Field<bool> &selection_field, - const eAttrDomain selection_domain) -{ - const CurveComponent &src_component = *geometry_set.get_component_for_read<CurveComponent>(); - GeometryComponentFieldContext field_context{src_component, selection_domain}; + CurveComponent &component = geometry_set.get_component_for_write<CurveComponent>(); + Curves &curves_id = *component.get_for_write(); + bke::CurvesGeometry &curves = bke::CurvesGeometry::wrap(curves_id.geometry); - fn::FieldEvaluator evaluator{field_context, - src_component.attribute_domain_num(selection_domain)}; - evaluator.add(selection_field); - evaluator.evaluate(); - const VArray_Span<bool> &selection = evaluator.get_evaluated<bool>(0); - std::unique_ptr<CurveEval> r_curve = curve_separate( - *curves_to_curve_eval(*src_component.get_for_read()), selection, selection_domain); - if (r_curve) { - geometry_set.replace_curves(curve_eval_to_curves(*r_curve)); + if (selection_domain == ATTR_DOMAIN_POINT) { + curves.remove_points(selection); } - else { - geometry_set.replace_curves(nullptr); + else if (selection_domain == ATTR_DOMAIN_CURVE) { + curves.remove_curves(selection); } } @@ -1224,7 +1098,8 @@ void separate_geometry(GeometrySet &geometry_set, } if (geometry_set.has_curves()) { if (ELEM(domain, ATTR_DOMAIN_POINT, ATTR_DOMAIN_CURVE)) { - file_ns::separate_curve_selection(geometry_set, selection_field, domain); + file_ns::delete_curves_selection( + geometry_set, fn::invert_boolean_field(selection_field), domain); some_valid_domain = true; } } |