From e0e95f789576fec43550ef8aae8ae94151f7967f Mon Sep 17 00:00:00 2001 From: Hans Goudey Date: Mon, 9 May 2022 17:33:30 +0200 Subject: Refactor: Move resample curves code to the geometry module This commit moves the code for the resample curves node to the geometry module, to allow reusing it in any editor. Split from D14870. --- source/blender/geometry/CMakeLists.txt | 2 + source/blender/geometry/GEO_resample_curves.hh | 39 ++ source/blender/geometry/intern/resample_curves.cc | 507 ++++++++++++++++++++++ 3 files changed, 548 insertions(+) create mode 100644 source/blender/geometry/GEO_resample_curves.hh create mode 100644 source/blender/geometry/intern/resample_curves.cc (limited to 'source/blender/geometry') 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 &selection_field, + const fn::Field &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 &selection_field, + const fn::Field &segment_length_field); + +/** + * Evaluate each selected curve to its implicit evaluated points. + */ +Curves *resample_to_evaluated(const CurveComponent &src_component, + const fn::Field &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 get_count_input_max_one(const fn::Field &count_field) +{ + static fn::CustomMF_SI_SO 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(max_one_fn, {count_field})); + + return fn::Field(std::move(clamp_op)); +} + +static fn::Field get_count_input_from_length(const fn::Field &length_field) +{ + static fn::CustomMF_SI_SI_SO 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( + get_count_fn, + {fn::Field(std::make_shared()), length_field})); + + return fn::Field(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 &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 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 ids, + const CurveComponent &src_component, + CurveComponent &dst_component, + Vector &src, + Vector &dst, + Vector &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 src; + Vector dst; + + Vector dst_attributes; + + Vector src_no_interpolation; + Vector 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 ids; + VectorSet 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 +static void copy_between_curves(const bke::CurvesGeometry &src_curves, + const bke::CurvesGeometry &dst_curves, + const Span curve_ranges, + const Span src, + const MutableSpan 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 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(), dst.typed()); + }); +} + +/** + * 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 curve_ranges, + MutableSpan 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 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 &selection_field, + const fn::Field &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 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 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 curves_cyclic = src_curves.cyclic(); + VArray curve_types = src_curves.curve_types(); + Span evaluated_positions = src_curves.evaluated_positions(); + MutableSpan 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 sample_indices(dst_curves.points_num()); + Array 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 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 src = attributes.src[i_attribute].typed(); + MutableSpan dst = attributes.dst[i_attribute].typed(); + + 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 evaluated = evaluated_buffer.as_mutable_span().cast(); + 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 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 &selection_field, + const fn::Field &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 &selection_field, + const fn::Field &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 &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 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 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 evaluated_positions = src_curves.evaluated_positions(); + MutableSpan 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 src = attributes.src[i_attribute].typed(); + MutableSpan dst = attributes.dst[i_attribute].typed(); + + 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 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 -- cgit v1.2.3