diff options
| -rw-r--r-- | source/blender/blenkernel/BKE_curves.hh | 1 | ||||
| -rw-r--r-- | source/blender/blenkernel/intern/curves.cc | 7 | ||||
| -rw-r--r-- | source/blender/geometry/CMakeLists.txt | 2 | ||||
| -rw-r--r-- | source/blender/geometry/GEO_resample_curves.hh | 39 | ||||
| -rw-r--r-- | source/blender/geometry/intern/resample_curves.cc | 507 | ||||
| -rw-r--r-- | source/blender/nodes/geometry/nodes/node_geo_curve_resample.cc | 537 |
6 files changed, 579 insertions, 514 deletions
diff --git a/source/blender/blenkernel/BKE_curves.hh b/source/blender/blenkernel/BKE_curves.hh index bf2d50f63be..8ef7d2811b1 100644 --- a/source/blender/blenkernel/BKE_curves.hh +++ b/source/blender/blenkernel/BKE_curves.hh @@ -671,6 +671,7 @@ void interpolate_to_evaluated(const BasisCache &basis_cache, } // namespace curves Curves *curves_new_nomain(int points_num, int curves_num); +Curves *curves_new_nomain(CurvesGeometry curves); /** * Create a new curves data-block containing a single curve with the given length and type. diff --git a/source/blender/blenkernel/intern/curves.cc b/source/blender/blenkernel/intern/curves.cc index 1df1492bac1..bcfd6206a78 100644 --- a/source/blender/blenkernel/intern/curves.cc +++ b/source/blender/blenkernel/intern/curves.cc @@ -379,4 +379,11 @@ Curves *curves_new_nomain_single(const int points_num, const CurveType type) return curves; } +Curves *curves_new_nomain(CurvesGeometry curves) +{ + Curves *curves_id = static_cast<Curves *>(BKE_id_new_nomain(ID_CV, nullptr)); + bke::CurvesGeometry::wrap(curves_id->geometry) = std::move(curves); + return curves_id; +} + } // namespace blender::bke diff --git a/source/blender/geometry/CMakeLists.txt b/source/blender/geometry/CMakeLists.txt index 8716d6c8f67..9dcacb13536 100644 --- a/source/blender/geometry/CMakeLists.txt +++ b/source/blender/geometry/CMakeLists.txt @@ -19,12 +19,14 @@ set(SRC intern/mesh_to_curve_convert.cc intern/point_merge_by_distance.cc intern/realize_instances.cc + intern/resample_curves.cc intern/uv_parametrizer.c GEO_mesh_merge_by_distance.hh GEO_mesh_to_curve.hh GEO_point_merge_by_distance.hh GEO_realize_instances.hh + GEO_resample_curves.hh GEO_uv_parametrizer.h ) diff --git a/source/blender/geometry/GEO_resample_curves.hh b/source/blender/geometry/GEO_resample_curves.hh new file mode 100644 index 00000000000..7cfb5dadde6 --- /dev/null +++ b/source/blender/geometry/GEO_resample_curves.hh @@ -0,0 +1,39 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ + +#pragma once + +#include "FN_field.hh" + +#include "BKE_geometry_set.hh" + +struct Curves; + +namespace blender::geometry { + +/** + * Create new curves where the selected curves have been resampled with a number of uniform-length + * samples defined by the count field. Interpolate attributes to the result, with an accuracy that + * depends on the curve's resolution parameter. + * + * \note The values provided by the #count_field are clampled to 1 or greater. + */ +Curves *resample_to_count(const CurveComponent &src_component, + const fn::Field<bool> &selection_field, + const fn::Field<int> &count_field); + +/** + * Create new curves resampled to make each segment have the length specified by the + * #segment_length field input, rounded to make the length of each segment the same. + * The accuracy will depend on the curve's resolution parameter. + */ +Curves *resample_to_length(const CurveComponent &src_component, + const fn::Field<bool> &selection_field, + const fn::Field<float> &segment_length_field); + +/** + * Evaluate each selected curve to its implicit evaluated points. + */ +Curves *resample_to_evaluated(const CurveComponent &src_component, + const fn::Field<bool> &selection_field); + +} // namespace blender::geometry diff --git a/source/blender/geometry/intern/resample_curves.cc b/source/blender/geometry/intern/resample_curves.cc new file mode 100644 index 00000000000..4f1fbfd29d1 --- /dev/null +++ b/source/blender/geometry/intern/resample_curves.cc @@ -0,0 +1,507 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ + +#include "BLI_length_parameterize.hh" +#include "BLI_task.hh" + +#include "FN_field.hh" +#include "FN_multi_function_builder.hh" + +#include "BKE_attribute_math.hh" +#include "BKE_curves.hh" +#include "BKE_geometry_fields.hh" + +#include "GEO_resample_curves.hh" + +namespace blender::geometry { + +static fn::Field<int> get_count_input_max_one(const fn::Field<int> &count_field) +{ + static fn::CustomMF_SI_SO<int, int> max_one_fn( + "Clamp Above One", + [](int value) { return std::max(1, value); }, + fn::CustomMF_presets::AllSpanOrSingle()); + auto clamp_op = std::make_shared<fn::FieldOperation>( + fn::FieldOperation(max_one_fn, {count_field})); + + return fn::Field<int>(std::move(clamp_op)); +} + +static fn::Field<int> get_count_input_from_length(const fn::Field<float> &length_field) +{ + static fn::CustomMF_SI_SI_SO<float, float, int> get_count_fn( + "Length Input to Count", + [](const float curve_length, const float sample_length) { + /* Find the number of sampled segments by dividing the total length by + * the sample length. Then there is one more sampled point than segment. */ + const int count = int(curve_length / sample_length) + 1; + return std::max(1, count); + }, + fn::CustomMF_presets::AllSpanOrSingle()); + + auto get_count_op = std::make_shared<fn::FieldOperation>(fn::FieldOperation( + get_count_fn, + {fn::Field<float>(std::make_shared<bke::CurveLengthFieldInput>()), length_field})); + + return fn::Field<int>(std::move(get_count_op)); +} + +/** + * Return true if the attribute should be copied/interpolated to the result curves. + * Don't output attributes that correspond to curve types that have no curves in the result. + */ +static bool interpolate_attribute_to_curves(const bke::AttributeIDRef &attribute_id, + const std::array<int, CURVE_TYPES_NUM> &type_counts) +{ + if (!attribute_id.is_named()) { + return true; + } + if (ELEM(attribute_id.name(), + "handle_type_left", + "handle_type_right", + "handle_left", + "handle_right")) { + return type_counts[CURVE_TYPE_BEZIER] != 0; + } + if (ELEM(attribute_id.name(), "nurbs_weight")) { + return type_counts[CURVE_TYPE_NURBS] != 0; + } + return true; +} + +/** + * Return true if the attribute should be copied to poly curves. + */ +static bool interpolate_attribute_to_poly_curve(const bke::AttributeIDRef &attribute_id) +{ + static const Set<StringRef> no_interpolation{{ + "handle_type_left", + "handle_type_right", + "handle_position_right", + "handle_position_left", + "nurbs_weight", + }}; + return !(attribute_id.is_named() && no_interpolation.contains(attribute_id.name())); +} + +/** + * Retrieve spans from source and result attributes. + */ +static void retrieve_attribute_spans(const Span<bke::AttributeIDRef> ids, + const CurveComponent &src_component, + CurveComponent &dst_component, + Vector<GSpan> &src, + Vector<GMutableSpan> &dst, + Vector<bke::OutputAttribute> &dst_attributes) +{ + for (const int i : ids.index_range()) { + GVArray src_attribute = src_component.attribute_try_get_for_read(ids[i], ATTR_DOMAIN_POINT); + BLI_assert(src_attribute); + src.append(src_attribute.get_internal_span()); + + const CustomDataType data_type = bke::cpp_type_to_custom_data_type(src_attribute.type()); + bke::OutputAttribute dst_attribute = dst_component.attribute_try_get_for_output_only( + ids[i], ATTR_DOMAIN_POINT, data_type); + dst.append(dst_attribute.as_span()); + dst_attributes.append(std::move(dst_attribute)); + } +} + +struct AttributesForInterpolation : NonCopyable, NonMovable { + Vector<GSpan> src; + Vector<GMutableSpan> dst; + + Vector<bke::OutputAttribute> dst_attributes; + + Vector<GSpan> src_no_interpolation; + Vector<GMutableSpan> dst_no_interpolation; +}; + +/** + * Gather a set of all generic attribute IDs to copy to the result curves. + */ +static void gather_point_attributes_to_interpolate(const CurveComponent &src_component, + CurveComponent &dst_component, + AttributesForInterpolation &result) +{ + bke::CurvesGeometry &dst_curves = bke::CurvesGeometry::wrap( + dst_component.get_for_write()->geometry); + + VectorSet<bke::AttributeIDRef> ids; + VectorSet<bke::AttributeIDRef> ids_no_interpolation; + src_component.attribute_foreach( + [&](const bke::AttributeIDRef &id, const AttributeMetaData meta_data) { + if (meta_data.domain != ATTR_DOMAIN_POINT) { + return true; + } + if (!interpolate_attribute_to_curves(id, dst_curves.curve_type_counts())) { + return true; + } + if (interpolate_attribute_to_poly_curve(id)) { + ids.add_new(id); + } + else { + ids_no_interpolation.add_new(id); + } + return true; + }); + + /* Position is handled differently since it has non-generic interpolation for Bezier + * curves and because the evaluated positions are cached for each evaluated point. */ + ids.remove_contained("position"); + + retrieve_attribute_spans( + ids, src_component, dst_component, result.src, result.dst, result.dst_attributes); + + /* Attributes that aren't interpolated like Bezier handles still have to be be copied + * to the result when there are any unselected curves of the corresponding type. */ + retrieve_attribute_spans(ids_no_interpolation, + src_component, + dst_component, + result.src_no_interpolation, + result.dst_no_interpolation, + result.dst_attributes); + + /* Copy the result curves with pointers to new attributes back to the original. */ + memcpy((void *)&dst_curves, &dst_component.get_for_write()->geometry, sizeof(CurvesGeometry)); + + dst_curves.update_customdata_pointers(); +} + +/** + * Copy the provided point attribute values between all curves in the #curve_ranges index + * ranges, assuming that all curves are the same size in #src_curves and #dst_curves. + */ +template<typename T> +static void copy_between_curves(const bke::CurvesGeometry &src_curves, + const bke::CurvesGeometry &dst_curves, + const Span<IndexRange> curve_ranges, + const Span<T> src, + const MutableSpan<T> dst) +{ + threading::parallel_for(curve_ranges.index_range(), 512, [&](IndexRange range) { + for (const IndexRange range : curve_ranges.slice(range)) { + const IndexRange src_points = src_curves.points_for_curves(range); + const IndexRange dst_points = dst_curves.points_for_curves(range); + /* The arrays might be large, so a threaded copy might make sense here too. */ + dst.slice(dst_points).copy_from(src.slice(src_points)); + } + }); +} +static void copy_between_curves(const bke::CurvesGeometry &src_curves, + const bke::CurvesGeometry &dst_curves, + const Span<IndexRange> unselected_ranges, + const GSpan src, + const GMutableSpan dst) +{ + attribute_math::convert_to_static_type(src.type(), [&](auto dummy) { + using T = decltype(dummy); + copy_between_curves(src_curves, dst_curves, unselected_ranges, src.typed<T>(), dst.typed<T>()); + }); +} + +/** + * Copy the size of every curve in #curve_ranges to the corresponding index in #counts. + */ +static void fill_curve_counts(const bke::CurvesGeometry &src_curves, + const Span<IndexRange> curve_ranges, + MutableSpan<int> counts) +{ + threading::parallel_for(curve_ranges.index_range(), 512, [&](IndexRange ranges_range) { + for (const IndexRange curves_range : curve_ranges.slice(ranges_range)) { + for (const int i : curves_range) { + counts[i] = src_curves.points_for_curve(i).size(); + } + } + }); +} + +/** + * Turn an array of sizes into the offset at each index including all previous sizes. + */ +static void accumulate_counts_to_offsets(MutableSpan<int> counts_to_offsets) +{ + int total = 0; + for (const int i : counts_to_offsets.index_range().drop_back(1)) { + const int count = counts_to_offsets[i]; + BLI_assert(count > 0); + counts_to_offsets[i] = total; + total += count; + } + counts_to_offsets.last() = total; +} + +static Curves *resample_to_uniform(const CurveComponent &src_component, + const fn::Field<bool> &selection_field, + const fn::Field<int> &count_field) +{ + const bke::CurvesGeometry &src_curves = bke::CurvesGeometry::wrap( + src_component.get_for_read()->geometry); + + /* Create the new curves without any points and evaluate the final count directly + * into the offsets array, in order to be accumulated into offsets later. */ + Curves *dst_curves_id = bke::curves_new_nomain(0, src_curves.curves_num()); + bke::CurvesGeometry &dst_curves = bke::CurvesGeometry::wrap(dst_curves_id->geometry); + + /* Directly copy curve attributes, since they stay the same (except for curve types). */ + CustomData_copy(&src_curves.curve_data, + &dst_curves.curve_data, + CD_MASK_ALL, + CD_DUPLICATE, + src_curves.curves_num()); + MutableSpan<int> dst_offsets = dst_curves.offsets_for_write(); + + bke::GeometryComponentFieldContext field_context{src_component, ATTR_DOMAIN_CURVE}; + fn::FieldEvaluator evaluator{field_context, src_curves.curves_num()}; + evaluator.set_selection(selection_field); + evaluator.add_with_destination(count_field, dst_offsets); + evaluator.evaluate(); + const IndexMask selection = evaluator.get_evaluated_selection_as_mask(); + const Vector<IndexRange> unselected_ranges = selection.extract_ranges_invert( + src_curves.curves_range(), nullptr); + + /* Fill the counts for the curves that aren't selected and accumulate the counts into offsets. */ + fill_curve_counts(src_curves, unselected_ranges, dst_offsets); + accumulate_counts_to_offsets(dst_offsets); + dst_curves.resize(dst_offsets.last(), dst_curves.curves_num()); + + /* All resampled curves are poly curves. */ + dst_curves.fill_curve_types(selection, CURVE_TYPE_POLY); + + VArray<bool> curves_cyclic = src_curves.cyclic(); + VArray<int8_t> curve_types = src_curves.curve_types(); + Span<float3> evaluated_positions = src_curves.evaluated_positions(); + MutableSpan<float3> dst_positions = dst_curves.positions_for_write(); + + AttributesForInterpolation attributes; + CurveComponent dst_component; + dst_component.replace(dst_curves_id, GeometryOwnershipType::Editable); + gather_point_attributes_to_interpolate(src_component, dst_component, attributes); + + src_curves.ensure_evaluated_lengths(); + + /* Sampling arbitrary attributes works by first interpolating them to the curve's standard + * "evaluated points" and then interpolating that result with the uniform samples. This is + * potentially wasteful when down-sampling a curve to many fewer points. There are two possible + * solutions: only sample the necessary points for interpolation, or first sample curve + * parameter/segment indices and evaluate the curve directly. */ + Array<int> sample_indices(dst_curves.points_num()); + Array<float> sample_factors(dst_curves.points_num()); + + /* Use a "for each group of curves: for each attribute: for each curve" pattern to work on + * smaller sections of data that ideally fit into CPU cache better than simply one attribute at a + * time or one curve at a time. */ + threading::parallel_for(selection.index_range(), 512, [&](IndexRange selection_range) { + const IndexMask sliced_selection = selection.slice(selection_range); + + Vector<std::byte> evaluated_buffer; + + /* Gather uniform samples based on the accumulated lengths of the original curve. */ + for (const int i_curve : sliced_selection) { + const bool cyclic = curves_cyclic[i_curve]; + const IndexRange dst_points = dst_curves.points_for_curve(i_curve); + length_parameterize::create_uniform_samples( + src_curves.evaluated_lengths_for_curve(i_curve, cyclic), + curves_cyclic[i_curve], + sample_indices.as_mutable_span().slice(dst_points), + sample_factors.as_mutable_span().slice(dst_points)); + } + + /* For every attribute, evaluate attributes from every curve in the range in the original + * curve's "evaluated points", then use linear interpolation to sample to the result. */ + for (const int i_attribute : attributes.dst.index_range()) { + attribute_math::convert_to_static_type(attributes.src[i_attribute].type(), [&](auto dummy) { + using T = decltype(dummy); + Span<T> src = attributes.src[i_attribute].typed<T>(); + MutableSpan<T> dst = attributes.dst[i_attribute].typed<T>(); + + for (const int i_curve : sliced_selection) { + const IndexRange src_points = src_curves.points_for_curve(i_curve); + const IndexRange dst_points = dst_curves.points_for_curve(i_curve); + + if (curve_types[i_curve] == CURVE_TYPE_POLY) { + length_parameterize::linear_interpolation(src.slice(src_points), + sample_indices.as_span().slice(dst_points), + sample_factors.as_span().slice(dst_points), + dst.slice(dst_points)); + } + else { + const int evaluated_size = src_curves.evaluated_points_for_curve(i_curve).size(); + evaluated_buffer.clear(); + evaluated_buffer.resize(sizeof(T) * evaluated_size); + MutableSpan<T> evaluated = evaluated_buffer.as_mutable_span().cast<T>(); + src_curves.interpolate_to_evaluated(i_curve, src.slice(src_points), evaluated); + + length_parameterize::linear_interpolation(evaluated.as_span(), + sample_indices.as_span().slice(dst_points), + sample_factors.as_span().slice(dst_points), + dst.slice(dst_points)); + } + } + }); + } + + /* Interpolate the evaluated positions to the resampled curves. */ + for (const int i_curve : sliced_selection) { + const IndexRange src_points = src_curves.evaluated_points_for_curve(i_curve); + const IndexRange dst_points = dst_curves.points_for_curve(i_curve); + length_parameterize::linear_interpolation(evaluated_positions.slice(src_points), + sample_indices.as_span().slice(dst_points), + sample_factors.as_span().slice(dst_points), + dst_positions.slice(dst_points)); + } + + /* Fill the default value for non-interpolating attributes that still must be copied. */ + for (GMutableSpan dst : attributes.dst_no_interpolation) { + for (const int i_curve : sliced_selection) { + const IndexRange dst_points = dst_curves.points_for_curve(i_curve); + dst.type().value_initialize_n(dst.slice(dst_points).data(), dst_points.size()); + } + } + }); + + /* Any attribute data from unselected curve points can be directly copied. */ + for (const int i : attributes.src.index_range()) { + copy_between_curves( + src_curves, dst_curves, unselected_ranges, attributes.src[i], attributes.dst[i]); + } + for (const int i : attributes.src_no_interpolation.index_range()) { + copy_between_curves(src_curves, + dst_curves, + unselected_ranges, + attributes.src_no_interpolation[i], + attributes.dst_no_interpolation[i]); + } + + /* Copy positions for unselected curves. */ + Span<float3> src_positions = src_curves.positions(); + copy_between_curves(src_curves, dst_curves, unselected_ranges, src_positions, dst_positions); + + for (bke::OutputAttribute &attribute : attributes.dst_attributes) { + attribute.save(); + } + + return dst_curves_id; +} + +Curves *resample_to_count(const CurveComponent &src_component, + const fn::Field<bool> &selection_field, + const fn::Field<int> &count_field) +{ + return resample_to_uniform(src_component, selection_field, get_count_input_max_one(count_field)); +} + +Curves *resample_to_length(const CurveComponent &src_component, + const fn::Field<bool> &selection_field, + const fn::Field<float> &segment_length_field) +{ + return resample_to_uniform( + src_component, selection_field, get_count_input_from_length(segment_length_field)); +} + +Curves *resample_to_evaluated(const CurveComponent &src_component, + const fn::Field<bool> &selection_field) +{ + const bke::CurvesGeometry &src_curves = bke::CurvesGeometry::wrap( + src_component.get_for_read()->geometry); + + bke::GeometryComponentFieldContext field_context{src_component, ATTR_DOMAIN_CURVE}; + fn::FieldEvaluator evaluator{field_context, src_curves.curves_num()}; + evaluator.set_selection(selection_field); + evaluator.evaluate(); + const IndexMask selection = evaluator.get_evaluated_selection_as_mask(); + const Vector<IndexRange> unselected_ranges = selection.extract_ranges_invert( + src_curves.curves_range(), nullptr); + + Curves *dst_curves_id = bke::curves_new_nomain(0, src_curves.curves_num()); + bke::CurvesGeometry &dst_curves = bke::CurvesGeometry::wrap(dst_curves_id->geometry); + + /* Directly copy curve attributes, since they stay the same (except for curve types). */ + CustomData_copy(&src_curves.curve_data, + &dst_curves.curve_data, + CD_MASK_ALL, + CD_DUPLICATE, + src_curves.curves_num()); + /* All resampled curves are poly curves. */ + dst_curves.fill_curve_types(selection, CURVE_TYPE_POLY); + MutableSpan<int> dst_offsets = dst_curves.offsets_for_write(); + + src_curves.ensure_evaluated_offsets(); + threading::parallel_for(selection.index_range(), 4096, [&](IndexRange range) { + for (const int i : selection.slice(range)) { + dst_offsets[i] = src_curves.evaluated_points_for_curve(i).size(); + } + }); + fill_curve_counts(src_curves, unselected_ranges, dst_offsets); + accumulate_counts_to_offsets(dst_offsets); + + dst_curves.resize(dst_offsets.last(), dst_curves.curves_num()); + + /* Create the correct number of uniform-length samples for every selected curve. */ + Span<float3> evaluated_positions = src_curves.evaluated_positions(); + MutableSpan<float3> dst_positions = dst_curves.positions_for_write(); + + AttributesForInterpolation attributes; + CurveComponent dst_component; + dst_component.replace(dst_curves_id, GeometryOwnershipType::Editable); + gather_point_attributes_to_interpolate(src_component, dst_component, attributes); + + threading::parallel_for(selection.index_range(), 512, [&](IndexRange selection_range) { + const IndexMask sliced_selection = selection.slice(selection_range); + + /* Evaluate generic point attributes directly to the result attributes. */ + for (const int i_attribute : attributes.dst.index_range()) { + attribute_math::convert_to_static_type(attributes.src[i_attribute].type(), [&](auto dummy) { + using T = decltype(dummy); + Span<T> src = attributes.src[i_attribute].typed<T>(); + MutableSpan<T> dst = attributes.dst[i_attribute].typed<T>(); + + for (const int i_curve : sliced_selection) { + const IndexRange src_points = src_curves.points_for_curve(i_curve); + const IndexRange dst_points = dst_curves.points_for_curve(i_curve); + src_curves.interpolate_to_evaluated( + i_curve, src.slice(src_points), dst.slice(dst_points)); + } + }); + } + + /* Copy the evaluated positions to the selected curves. */ + for (const int i_curve : sliced_selection) { + const IndexRange src_points = src_curves.evaluated_points_for_curve(i_curve); + const IndexRange dst_points = dst_curves.points_for_curve(i_curve); + dst_positions.slice(dst_points).copy_from(evaluated_positions.slice(src_points)); + } + + /* Fill the default value for non-interpolating attributes that still must be copied. */ + for (GMutableSpan dst : attributes.dst_no_interpolation) { + for (const int i_curve : sliced_selection) { + const IndexRange dst_points = dst_curves.points_for_curve(i_curve); + dst.type().value_initialize_n(dst.slice(dst_points).data(), dst_points.size()); + } + } + }); + + /* Any attribute data from unselected curve points can be directly copied. */ + for (const int i : attributes.src.index_range()) { + copy_between_curves( + src_curves, dst_curves, unselected_ranges, attributes.src[i], attributes.dst[i]); + } + for (const int i : attributes.src_no_interpolation.index_range()) { + copy_between_curves(src_curves, + dst_curves, + unselected_ranges, + attributes.src_no_interpolation[i], + attributes.dst_no_interpolation[i]); + } + + /* Copy positions for unselected curves. */ + Span<float3> src_positions = src_curves.positions(); + copy_between_curves(src_curves, dst_curves, unselected_ranges, src_positions, dst_positions); + + for (bke::OutputAttribute &attribute : attributes.dst_attributes) { + attribute.save(); + } + + return dst_curves_id; +} + +} // namespace blender::geometry diff --git a/source/blender/nodes/geometry/nodes/node_geo_curve_resample.cc b/source/blender/nodes/geometry/nodes/node_geo_curve_resample.cc index 471d6af560f..d9cc8bcf023 100644 --- a/source/blender/nodes/geometry/nodes/node_geo_curve_resample.cc +++ b/source/blender/nodes/geometry/nodes/node_geo_curve_resample.cc @@ -1,12 +1,7 @@ /* SPDX-License-Identifier: GPL-2.0-or-later */ -#include "BLI_array.hh" -#include "BLI_index_mask_ops.hh" -#include "BLI_length_parameterize.hh" -#include "BLI_task.hh" -#include "BLI_timeit.hh" +#include "GEO_resample_curves.hh" -#include "BKE_attribute_math.hh" #include "BKE_curves.hh" #include "UI_interface.h" @@ -56,495 +51,6 @@ static void node_update(bNodeTree *ntree, bNode *node) nodeSetSocketAvailability(ntree, length_socket, mode == GEO_NODE_CURVE_RESAMPLE_LENGTH); } -/** - * Return true if the attribute should be copied/interpolated to the result curves. - * Don't output attributes that correspond to curve types that have no curves in the result. - */ -static bool interpolate_attribute_to_curves(const AttributeIDRef &attribute_id, - const std::array<int, CURVE_TYPES_NUM> &type_counts) -{ - if (!attribute_id.is_named()) { - return true; - } - if (ELEM(attribute_id.name(), - "handle_type_left", - "handle_type_right", - "handle_left", - "handle_right")) { - return type_counts[CURVE_TYPE_BEZIER] != 0; - } - if (ELEM(attribute_id.name(), "nurbs_weight")) { - return type_counts[CURVE_TYPE_NURBS] != 0; - } - return true; -} - -/** - * Return true if the attribute should be copied to poly curves. - */ -static bool interpolate_attribute_to_poly_curve(const AttributeIDRef &attribute_id) -{ - static const Set<StringRef> no_interpolation{{ - "handle_type_left", - "handle_type_right", - "handle_position_right", - "handle_position_left", - "nurbs_weight", - }}; - return !(attribute_id.is_named() && no_interpolation.contains(attribute_id.name())); -} - -/** - * Retrieve spans from source and result attributes. - */ -static void retrieve_attribute_spans(const Span<AttributeIDRef> ids, - const CurveComponent &src_component, - CurveComponent &dst_component, - Vector<GSpan> &src, - Vector<GMutableSpan> &dst, - Vector<OutputAttribute> &dst_attributes) -{ - for (const int i : ids.index_range()) { - GVArray src_attribute = src_component.attribute_try_get_for_read(ids[i], ATTR_DOMAIN_POINT); - BLI_assert(src_attribute); - src.append(src_attribute.get_internal_span()); - - const CustomDataType data_type = bke::cpp_type_to_custom_data_type(src_attribute.type()); - OutputAttribute dst_attribute = dst_component.attribute_try_get_for_output_only( - ids[i], ATTR_DOMAIN_POINT, data_type); - dst.append(dst_attribute.as_span()); - dst_attributes.append(std::move(dst_attribute)); - } -} - -struct AttributesForInterpolation : NonCopyable, NonMovable { - Vector<GSpan> src; - Vector<GMutableSpan> dst; - - Vector<OutputAttribute> dst_attributes; - - Vector<GSpan> src_no_interpolation; - Vector<GMutableSpan> dst_no_interpolation; -}; - -/** - * Gather a set of all generic attribute IDs to copy to the result curves. - */ -static void gather_point_attributes_to_interpolate(const CurveComponent &src_component, - CurveComponent &dst_component, - AttributesForInterpolation &result) -{ - const Curves &dst_curves_id = *dst_component.get_for_read(); - const bke::CurvesGeometry &dst_curves = bke::CurvesGeometry::wrap(dst_curves_id.geometry); - - VectorSet<AttributeIDRef> ids; - VectorSet<AttributeIDRef> ids_no_interpolation; - src_component.attribute_foreach( - [&](const AttributeIDRef &id, const AttributeMetaData meta_data) { - if (meta_data.domain != ATTR_DOMAIN_POINT) { - return true; - } - if (!interpolate_attribute_to_curves(id, dst_curves.curve_type_counts())) { - return true; - } - if (interpolate_attribute_to_poly_curve(id)) { - ids.add_new(id); - } - else { - ids_no_interpolation.add_new(id); - } - return true; - }); - - /* Position is handled differently since it has non-generic interpolation for Bezier - * curves and because the evaluated positions are cached for each evaluated point. */ - ids.remove_contained("position"); - - retrieve_attribute_spans( - ids, src_component, dst_component, result.src, result.dst, result.dst_attributes); - - /* Attributes that aren't interpolated like Bezier handles still have to be be copied - * to the result when there are any unselected curves of the corresponding type. */ - retrieve_attribute_spans(ids_no_interpolation, - src_component, - dst_component, - result.src_no_interpolation, - result.dst_no_interpolation, - result.dst_attributes); -} - -/** - * Copy the provided point attribute values between all curves in the #curve_ranges index - * ranges, assuming that all curves are the same size in #src_curves and #dst_curves. - */ -template<typename T> -static void copy_between_curves(const bke::CurvesGeometry &src_curves, - const bke::CurvesGeometry &dst_curves, - const Span<IndexRange> curve_ranges, - const Span<T> src, - const MutableSpan<T> dst) -{ - threading::parallel_for(curve_ranges.index_range(), 512, [&](IndexRange range) { - for (const IndexRange range : curve_ranges.slice(range)) { - const IndexRange src_points = src_curves.points_for_curves(range); - const IndexRange dst_points = dst_curves.points_for_curves(range); - /* The arrays might be large, so a threaded copy might make sense here too. */ - dst.slice(dst_points).copy_from(src.slice(src_points)); - } - }); -} -static void copy_between_curves(const bke::CurvesGeometry &src_curves, - const bke::CurvesGeometry &dst_curves, - const Span<IndexRange> unselected_ranges, - const GSpan src, - const GMutableSpan dst) -{ - attribute_math::convert_to_static_type(src.type(), [&](auto dummy) { - using T = decltype(dummy); - copy_between_curves(src_curves, dst_curves, unselected_ranges, src.typed<T>(), dst.typed<T>()); - }); -} - -/** - * Copy the size of every curve in #curve_ranges to the corresponding index in #counts. - */ -static void fill_curve_counts(const bke::CurvesGeometry &src_curves, - const Span<IndexRange> curve_ranges, - MutableSpan<int> counts) -{ - threading::parallel_for(curve_ranges.index_range(), 512, [&](IndexRange ranges_range) { - for (const IndexRange curves_range : curve_ranges.slice(ranges_range)) { - for (const int i : curves_range) { - counts[i] = src_curves.points_for_curve(i).size(); - } - } - }); -} - -/** - * Turn an array of sizes into the offset at each index including all previous sizes. - */ -static void accumulate_counts_to_offsets(MutableSpan<int> counts_to_offsets) -{ - int total = 0; - for (const int i : counts_to_offsets.index_range().drop_back(1)) { - const int count = counts_to_offsets[i]; - BLI_assert(count > 0); - counts_to_offsets[i] = total; - total += count; - } - counts_to_offsets.last() = total; -} - -/** - * Create new curves where the selected curves have been resampled with a number of uniform-length - * samples defined by the count field. Interpolate attributes to the result, with an accuracy that - * depends on the curve's resolution parameter. - * - * \warning The values provided by the #count_field must be 1 or greater. - * \warning Curves with no evaluated points must not be selected. - */ -static Curves *resample_to_uniform_count(const CurveComponent &src_component, - const Field<bool> &selection_field, - const Field<int> &count_field) -{ - const Curves &src_curves_id = *src_component.get_for_read(); - const bke::CurvesGeometry &src_curves = bke::CurvesGeometry::wrap(src_curves_id.geometry); - - /* Create the new curves without any points and evaluate the final count directly - * into the offsets array, in order to be accumulated into offsets later. */ - Curves *dst_curves_id = bke::curves_new_nomain(0, src_curves.curves_num()); - bke::CurvesGeometry &dst_curves = bke::CurvesGeometry::wrap(dst_curves_id->geometry); - CurveComponent dst_component; - dst_component.replace(dst_curves_id, GeometryOwnershipType::Editable); - /* Directly copy curve attributes, since they stay the same (except for curve types). */ - CustomData_copy(&src_curves.curve_data, - &dst_curves.curve_data, - CD_MASK_ALL, - CD_DUPLICATE, - src_curves.curves_num()); - MutableSpan<int> dst_offsets = dst_curves.offsets_for_write(); - - GeometryComponentFieldContext field_context{src_component, ATTR_DOMAIN_CURVE}; - fn::FieldEvaluator evaluator{field_context, src_curves.curves_num()}; - evaluator.set_selection(selection_field); - evaluator.add_with_destination(count_field, dst_offsets); - evaluator.evaluate(); - const IndexMask selection = evaluator.get_evaluated_selection_as_mask(); - const Vector<IndexRange> unselected_ranges = selection.extract_ranges_invert( - src_curves.curves_range(), nullptr); - - /* Fill the counts for the curves that aren't selected and accumulate the counts into offsets. */ - fill_curve_counts(src_curves, unselected_ranges, dst_offsets); - accumulate_counts_to_offsets(dst_offsets); - dst_curves.resize(dst_offsets.last(), dst_curves.curves_num()); - - /* All resampled curves are poly curves. */ - dst_curves.fill_curve_types(selection, CURVE_TYPE_POLY); - - VArray<bool> curves_cyclic = src_curves.cyclic(); - VArray<int8_t> curve_types = src_curves.curve_types(); - Span<float3> evaluated_positions = src_curves.evaluated_positions(); - MutableSpan<float3> dst_positions = dst_curves.positions_for_write(); - - AttributesForInterpolation attributes; - gather_point_attributes_to_interpolate(src_component, dst_component, attributes); - - src_curves.ensure_evaluated_lengths(); - - /* Sampling arbitrary attributes works by first interpolating them to the curve's standard - * "evaluated points" and then interpolating that result with the uniform samples. This is - * potentially wasteful when down-sampling a curve to many fewer points. There are two possible - * solutions: only sample the necessary points for interpolation, or first sample curve - * parameter/segment indices and evaluate the curve directly. */ - Array<int> sample_indices(dst_curves.points_num()); - Array<float> sample_factors(dst_curves.points_num()); - - /* Use a "for each group of curves: for each attribute: for each curve" pattern to work on - * smaller sections of data that ideally fit into CPU cache better than simply one attribute at a - * time or one curve at a time. */ - threading::parallel_for(selection.index_range(), 512, [&](IndexRange selection_range) { - const IndexMask sliced_selection = selection.slice(selection_range); - - Vector<std::byte> evaluated_buffer; - - /* Gather uniform samples based on the accumulated lengths of the original curve. */ - for (const int i_curve : sliced_selection) { - const bool cyclic = curves_cyclic[i_curve]; - const IndexRange dst_points = dst_curves.points_for_curve(i_curve); - length_parameterize::create_uniform_samples( - src_curves.evaluated_lengths_for_curve(i_curve, cyclic), - curves_cyclic[i_curve], - sample_indices.as_mutable_span().slice(dst_points), - sample_factors.as_mutable_span().slice(dst_points)); - } - - /* For every attribute, evaluate attributes from every curve in the range in the original - * curve's "evaluated points", then use linear interpolation to sample to the result. */ - for (const int i_attribute : attributes.dst.index_range()) { - attribute_math::convert_to_static_type(attributes.src[i_attribute].type(), [&](auto dummy) { - using T = decltype(dummy); - Span<T> src = attributes.src[i_attribute].typed<T>(); - MutableSpan<T> dst = attributes.dst[i_attribute].typed<T>(); - - for (const int i_curve : sliced_selection) { - const IndexRange src_points = src_curves.points_for_curve(i_curve); - const IndexRange dst_points = dst_curves.points_for_curve(i_curve); - - if (curve_types[i_curve] == CURVE_TYPE_POLY) { - length_parameterize::linear_interpolation(src.slice(src_points), - sample_indices.as_span().slice(dst_points), - sample_factors.as_span().slice(dst_points), - dst.slice(dst_points)); - } - else { - const int evaluated_size = src_curves.evaluated_points_for_curve(i_curve).size(); - evaluated_buffer.clear(); - evaluated_buffer.resize(sizeof(T) * evaluated_size); - MutableSpan<T> evaluated = evaluated_buffer.as_mutable_span().cast<T>(); - src_curves.interpolate_to_evaluated(i_curve, src.slice(src_points), evaluated); - - length_parameterize::linear_interpolation(evaluated.as_span(), - sample_indices.as_span().slice(dst_points), - sample_factors.as_span().slice(dst_points), - dst.slice(dst_points)); - } - } - }); - } - - /* Interpolate the evaluated positions to the resampled curves. */ - for (const int i_curve : sliced_selection) { - const IndexRange src_points = src_curves.evaluated_points_for_curve(i_curve); - const IndexRange dst_points = dst_curves.points_for_curve(i_curve); - length_parameterize::linear_interpolation(evaluated_positions.slice(src_points), - sample_indices.as_span().slice(dst_points), - sample_factors.as_span().slice(dst_points), - dst_positions.slice(dst_points)); - } - - /* Fill the default value for non-interpolating attributes that still must be copied. */ - for (GMutableSpan dst : attributes.dst_no_interpolation) { - for (const int i_curve : sliced_selection) { - const IndexRange dst_points = dst_curves.points_for_curve(i_curve); - dst.type().value_initialize_n(dst.slice(dst_points).data(), dst_points.size()); - } - } - }); - - /* Any attribute data from unselected curve points can be directly copied. */ - for (const int i : attributes.src.index_range()) { - copy_between_curves( - src_curves, dst_curves, unselected_ranges, attributes.src[i], attributes.dst[i]); - } - for (const int i : attributes.src_no_interpolation.index_range()) { - copy_between_curves(src_curves, - dst_curves, - unselected_ranges, - attributes.src_no_interpolation[i], - attributes.dst_no_interpolation[i]); - } - - /* Copy positions for unselected curves. */ - Span<float3> src_positions = src_curves.positions(); - copy_between_curves(src_curves, dst_curves, unselected_ranges, src_positions, dst_positions); - - for (OutputAttribute &attribute : attributes.dst_attributes) { - attribute.save(); - } - - return dst_curves_id; -} - -/** - * Evaluate each selected curve to its implicit evaluated points. - */ -static Curves *resample_to_evaluated(const CurveComponent &src_component, - const Field<bool> &selection_field) -{ - const Curves &src_curves_id = *src_component.get_for_read(); - const bke::CurvesGeometry &src_curves = bke::CurvesGeometry::wrap(src_curves_id.geometry); - - GeometryComponentFieldContext field_context{src_component, ATTR_DOMAIN_CURVE}; - fn::FieldEvaluator evaluator{field_context, src_curves.curves_num()}; - evaluator.set_selection(selection_field); - evaluator.evaluate(); - const IndexMask selection = evaluator.get_evaluated_selection_as_mask(); - const Vector<IndexRange> unselected_ranges = selection.extract_ranges_invert( - src_curves.curves_range(), nullptr); - - Curves *dst_curves_id = bke::curves_new_nomain(0, src_curves.curves_num()); - bke::CurvesGeometry &dst_curves = bke::CurvesGeometry::wrap(dst_curves_id->geometry); - CurveComponent dst_component; - dst_component.replace(dst_curves_id, GeometryOwnershipType::Editable); - /* Directly copy curve attributes, since they stay the same (except for curve types). */ - CustomData_copy(&src_curves.curve_data, - &dst_curves.curve_data, - CD_MASK_ALL, - CD_DUPLICATE, - src_curves.curves_num()); - /* All resampled curves are poly curves. */ - dst_curves.fill_curve_types(selection, CURVE_TYPE_POLY); - MutableSpan<int> dst_offsets = dst_curves.offsets_for_write(); - - src_curves.ensure_evaluated_offsets(); - threading::parallel_for(selection.index_range(), 4096, [&](IndexRange range) { - for (const int i : selection.slice(range)) { - dst_offsets[i] = src_curves.evaluated_points_for_curve(i).size(); - } - }); - fill_curve_counts(src_curves, unselected_ranges, dst_offsets); - accumulate_counts_to_offsets(dst_offsets); - - dst_curves.resize(dst_offsets.last(), dst_curves.curves_num()); - - /* Create the correct number of uniform-length samples for every selected curve. */ - Span<float3> evaluated_positions = src_curves.evaluated_positions(); - MutableSpan<float3> dst_positions = dst_curves.positions_for_write(); - - AttributesForInterpolation attributes; - gather_point_attributes_to_interpolate(src_component, dst_component, attributes); - - threading::parallel_for(selection.index_range(), 512, [&](IndexRange selection_range) { - const IndexMask sliced_selection = selection.slice(selection_range); - - /* Evaluate generic point attributes directly to the result attributes. */ - for (const int i_attribute : attributes.dst.index_range()) { - attribute_math::convert_to_static_type(attributes.src[i_attribute].type(), [&](auto dummy) { - using T = decltype(dummy); - Span<T> src = attributes.src[i_attribute].typed<T>(); - MutableSpan<T> dst = attributes.dst[i_attribute].typed<T>(); - - for (const int i_curve : sliced_selection) { - const IndexRange src_points = src_curves.points_for_curve(i_curve); - const IndexRange dst_points = dst_curves.points_for_curve(i_curve); - src_curves.interpolate_to_evaluated( - i_curve, src.slice(src_points), dst.slice(dst_points)); - } - }); - } - - /* Copy the evaluated positions to the selected curves. */ - for (const int i_curve : sliced_selection) { - const IndexRange src_points = src_curves.evaluated_points_for_curve(i_curve); - const IndexRange dst_points = dst_curves.points_for_curve(i_curve); - dst_positions.slice(dst_points).copy_from(evaluated_positions.slice(src_points)); - } - - /* Fill the default value for non-interpolating attributes that still must be copied. */ - for (GMutableSpan dst : attributes.dst_no_interpolation) { - for (const int i_curve : sliced_selection) { - const IndexRange dst_points = dst_curves.points_for_curve(i_curve); - dst.type().value_initialize_n(dst.slice(dst_points).data(), dst_points.size()); - } - } - }); - - /* Any attribute data from unselected curve points can be directly copied. */ - for (const int i : attributes.src.index_range()) { - copy_between_curves( - src_curves, dst_curves, unselected_ranges, attributes.src[i], attributes.dst[i]); - } - for (const int i : attributes.src_no_interpolation.index_range()) { - copy_between_curves(src_curves, - dst_curves, - unselected_ranges, - attributes.src_no_interpolation[i], - attributes.dst_no_interpolation[i]); - } - - /* Copy positions for unselected curves. */ - Span<float3> src_positions = src_curves.positions(); - copy_between_curves(src_curves, dst_curves, unselected_ranges, src_positions, dst_positions); - - for (OutputAttribute &attribute : attributes.dst_attributes) { - attribute.save(); - } - - return dst_curves_id; -} - -/** - * Create a resampled curve point count field for both "uniform" options. - * The complexity is handled here in order to make the actual resampling functions simpler. - */ -static Field<int> get_curve_count_field(GeoNodeExecParams params, - const GeometryNodeCurveResampleMode mode) -{ - if (mode == GEO_NODE_CURVE_RESAMPLE_COUNT) { - static fn::CustomMF_SI_SO<int, int> max_one_fn( - "Clamp Above One", - [](int value) { return std::max(1, value); }, - fn::CustomMF_presets::AllSpanOrSingle()); - auto clamp_op = std::make_shared<FieldOperation>( - FieldOperation(max_one_fn, {Field<int>(params.extract_input<Field<int>>("Count"))})); - - return Field<int>(std::move(clamp_op)); - } - - if (mode == GEO_NODE_CURVE_RESAMPLE_LENGTH) { - static fn::CustomMF_SI_SI_SO<float, float, int> get_count_fn( - "Length Input to Count", - [](const float curve_length, const float sample_length) { - /* Find the number of sampled segments by dividing the total length by - * the sample length. Then there is one more sampled point than segment. */ - const int count = int(curve_length / sample_length) + 1; - return std::max(1, count); - }, - fn::CustomMF_presets::AllSpanOrSingle()); - - auto get_count_op = std::make_shared<FieldOperation>( - FieldOperation(get_count_fn, - {Field<float>(std::make_shared<bke::CurveLengthFieldInput>()), - params.extract_input<Field<float>>("Length")})); - - return Field<int>(std::move(get_count_op)); - } - - BLI_assert_unreachable(); - return {}; -} - static void node_geo_exec(GeoNodeExecParams params) { GeometrySet geometry_set = params.extract_input<GeometrySet>("Curve"); @@ -555,32 +61,35 @@ static void node_geo_exec(GeoNodeExecParams params) const Field<bool> selection = params.extract_input<Field<bool>>("Selection"); switch (mode) { - case GEO_NODE_CURVE_RESAMPLE_COUNT: + case GEO_NODE_CURVE_RESAMPLE_COUNT: { + Field<int> count = params.extract_input<Field<int>>("Count"); + geometry_set.modify_geometry_sets([&](GeometrySet &geometry) { + if (const CurveComponent *component = geometry.get_component_for_read<CurveComponent>()) { + if (!component->is_empty()) { + geometry.replace_curves(geometry::resample_to_count(*component, selection, count)); + } + } + }); + break; + } case GEO_NODE_CURVE_RESAMPLE_LENGTH: { - Field<int> count = get_curve_count_field(params, mode); - - geometry_set.modify_geometry_sets([&](GeometrySet &geometry_set) { - if (!geometry_set.has_curves()) { - return; + Field<int> length = params.extract_input<Field<float>>("Length"); + geometry_set.modify_geometry_sets([&](GeometrySet &geometry) { + if (const CurveComponent *component = geometry.get_component_for_read<CurveComponent>()) { + if (!component->is_empty()) { + geometry.replace_curves(geometry::resample_to_length(*component, selection, length)); + } } - - Curves *result = resample_to_uniform_count( - *geometry_set.get_component_for_read<CurveComponent>(), selection, count); - - geometry_set.replace_curves(result); }); break; } case GEO_NODE_CURVE_RESAMPLE_EVALUATED: - geometry_set.modify_geometry_sets([&](GeometrySet &geometry_set) { - if (!geometry_set.has_curves()) { - return; + geometry_set.modify_geometry_sets([&](GeometrySet &geometry) { + if (const CurveComponent *component = geometry.get_component_for_read<CurveComponent>()) { + if (!component->is_empty()) { + geometry.replace_curves(geometry::resample_to_evaluated(*component, selection)); + } } - - Curves *result = resample_to_evaluated( - *geometry_set.get_component_for_read<CurveComponent>(), selection); - - geometry_set.replace_curves(result); }); break; } |