From ab444a80a280e125b3e4d002941504d56f340ced Mon Sep 17 00:00:00 2001 From: Jacques Lucke Date: Sat, 2 Jul 2022 21:51:45 +0200 Subject: BLI: refactor length parameterization This refactor had two main goals: * Simplify the sampling code by using an algorithm with fewer special cases. * Generalize the sampling to support non-sorted samples. The `SampleSegmentHint` optimization was inspired by `ValueAccessor` from OpenVDB and improves performance 2x in my test cases. Differential Revision: https://developer.blender.org/D15348 --- source/blender/blenlib/BLI_length_parameterize.hh | 133 +++++++++++++----- .../blender/blenlib/intern/length_parameterize.cc | 150 +++++---------------- .../blenlib/tests/BLI_length_parameterize_test.cc | 20 +-- .../editors/sculpt_paint/curves_sculpt_brush.cc | 5 +- source/blender/geometry/intern/resample_curves.cc | 9 +- 5 files changed, 147 insertions(+), 170 deletions(-) diff --git a/source/blender/blenlib/BLI_length_parameterize.hh b/source/blender/blenlib/BLI_length_parameterize.hh index ec0fabb75b4..ff957d92263 100644 --- a/source/blender/blenlib/BLI_length_parameterize.hh +++ b/source/blender/blenlib/BLI_length_parameterize.hh @@ -19,7 +19,7 @@ namespace blender::length_parameterize { * * \note This is the same as #bke::curves::curve_segment_num. */ -inline int lengths_num(const int points_num, const bool cyclic) +inline int segments_num(const int points_num, const bool cyclic) { return cyclic ? points_num : points_num - 1; } @@ -30,7 +30,7 @@ inline int lengths_num(const int points_num, const bool cyclic) template void accumulate_lengths(const Span values, const bool cyclic, MutableSpan lengths) { - BLI_assert(lengths.size() == lengths_num(values.size(), cyclic)); + BLI_assert(lengths.size() == segments_num(values.size(), cyclic)); float length = 0.0f; for (const int i : IndexRange(values.size() - 1)) { length += math::distance(values[i], values[i + 1]); @@ -42,57 +42,122 @@ void accumulate_lengths(const Span values, const bool cyclic, MutableSpan -void linear_interpolation(const Span src, - const Span indices, - const Span factors, - MutableSpan dst) +inline void linear_interpolation(const Span src, + const Span indices, + const Span factors, + MutableSpan dst) { BLI_assert(indices.size() == factors.size()); BLI_assert(indices.size() == dst.size()); - const int last_src_index = src.index_range().last(); + const int last_src_index = src.size() - 1; - int cyclic_sample_count = 0; - for (int i = indices.index_range().last(); i > 0; i--) { - if (indices[i] != last_src_index) { - break; + for (const int i : dst.index_range()) { + const int prev_index = indices[i]; + const float factor = factors[i]; + const bool is_cyclic_case = prev_index == last_src_index; + if (is_cyclic_case) { + dst[i] = math::interpolate(src.last(), src.first(), factor); + } + else { + dst[i] = math::interpolate(src[prev_index], src[prev_index + 1], factor); + } + } +} + +/** + * Passing this to consecutive calls of #sample_at_length can increase performance. + */ +struct SampleSegmentHint { + int segment_index = -1; + float segment_start; + float segment_length_inv; +}; + +/** + * \param accumulated_segment_lengths: Lengths of individual segments added up. + * \param sample_length: The position to sample at. + * \param r_segment_index: Returns the index of the segment that #sample_length is in. + * \param r_factor: Returns the position within the segment. + * + * \note #sample_length must not be outside of any segment. + */ +inline void sample_at_length(const Span accumulated_segment_lengths, + float sample_length, + int &r_segment_index, + float &r_factor, + SampleSegmentHint *hint = nullptr) +{ + /* Use a shorter variable name. */ + const Span lengths = accumulated_segment_lengths; + + BLI_assert(lengths.size() > 0); + BLI_assert(sample_length >= 0.0f); + BLI_assert(sample_length <= lengths.last()); + + if (hint != nullptr && hint->segment_index >= 0) { + const float length_in_segment = sample_length - hint->segment_start; + const float factor = length_in_segment * hint->segment_length_inv; + if (factor >= 0.0f && factor < 1.0f) { + r_segment_index = hint->segment_index; + r_factor = factor; + return; } - dst[i] = math::interpolate(src.last(), src.first(), factors[i]); - cyclic_sample_count++; } - for (const int i : dst.index_range().drop_back(cyclic_sample_count)) { - dst[i] = math::interpolate(src[indices[i]], src[indices[i] + 1], factors[i]); + const float total_length = lengths.last(); + if (sample_length >= total_length) { + /* Return the last position on the last segment. */ + r_segment_index = lengths.size() - 1; + r_factor = 1.0f; + return; + } + + const int prev_point_index = std::upper_bound(lengths.begin(), lengths.end(), sample_length) - + lengths.begin(); + const float segment_start = prev_point_index == 0 ? 0.0f : lengths[prev_point_index - 1]; + const float segment_end = lengths[prev_point_index]; + const float segment_length = segment_end - segment_start; + const float segment_length_inv = safe_divide(1.0f, segment_length); + const float length_in_segment = sample_length - segment_start; + const float factor = length_in_segment * segment_length_inv; + + r_segment_index = prev_point_index; + r_factor = factor; + + if (hint != nullptr) { + hint->segment_index = r_segment_index; + hint->segment_start = segment_start; + hint->segment_length_inv = segment_length_inv; } } /** - * Find the given number of points, evenly spaced along the provided length. For non-cyclic - * sequences, the first point will always be included, and last point will always be included if - * the #count is greater than zero. For cyclic sequences, the first point will always be included. + * Find evenly spaced samples along the lengths. * - * \warning The #count argument must be greater than zero. + * \param accumulated_segment_lengths: The accumulated lengths of the original elements being + * sampled. Could be calculated by #accumulate_lengths. + * \param include_last_point: Generally false for cyclic sequences and true otherwise. + * \param r_segment_indices: The index of the previous point at each sample. + * \param r_factors: The portion of the length in each segment at each sample. */ -void create_uniform_samples(Span lengths, - bool cyclic, - MutableSpan indices, - MutableSpan factors); +void sample_uniform(Span accumulated_segment_lengths, + bool include_last_point, + MutableSpan r_segment_indices, + MutableSpan r_factors); /** * For each provided sample length, find the segment index and interpolation factor. * - * \param lengths: The accumulated lengths of the original elements being sampled. - * Could be calculated by #accumulate_lengths. + * \param accumulated_segment_lengths: The accumulated lengths of the original elements being + * sampled. Could be calculated by #accumulate_lengths. * \param sample_lengths: Sampled locations in the #lengths array. Must be sorted and is expected * to be within the range of the #lengths values. - * \param cyclic: Whether the points described by the #lengths input is cyclic. This is likely - * redundant information theoretically. - * \param indices: The index of the previous point at each sample. - * \param factors: The portion of the length in each segment at each sample. + * \param r_segment_indices: The index of the previous point at each sample. + * \param r_factors: The portion of the length in each segment at each sample. */ -void create_samples_from_sorted_lengths(Span lengths, - Span sample_lengths, - bool cyclic, - MutableSpan indices, - MutableSpan factors); +void sample_at_lengths(Span accumulated_segment_lengths, + Span sample_lengths, + MutableSpan r_segment_indices, + MutableSpan r_factors); } // namespace blender::length_parameterize diff --git a/source/blender/blenlib/intern/length_parameterize.cc b/source/blender/blenlib/intern/length_parameterize.cc index e18b048e96d..06cca281510 100644 --- a/source/blender/blenlib/intern/length_parameterize.cc +++ b/source/blender/blenlib/intern/length_parameterize.cc @@ -1,144 +1,58 @@ /* SPDX-License-Identifier: GPL-2.0-or-later */ #include "BLI_length_parameterize.hh" +#include "BLI_task.hh" namespace blender::length_parameterize { -void create_uniform_samples(const Span lengths, - const bool cyclic, - MutableSpan indices, - MutableSpan factors) +void sample_uniform(const Span lengths, + const bool include_last_point, + MutableSpan r_segment_indices, + MutableSpan r_factors) { - const int count = indices.size(); + const int count = r_segment_indices.size(); BLI_assert(count > 0); BLI_assert(lengths.size() >= 1); BLI_assert(std::is_sorted(lengths.begin(), lengths.end())); - const int segments_num = lengths.size(); - const int points_num = cyclic ? segments_num : segments_num + 1; - indices.first() = 0; - factors.first() = 0.0f; if (count == 1) { + r_segment_indices[0] = 0; + r_factors[0] = 0.0f; return; } - const float total_length = lengths.last(); - if (total_length == 0.0f) { - indices.fill(0); - factors.fill(0.0f); - return; - } - - const float step_length = total_length / (count - (cyclic ? 0 : 1)); - const float step_length_inv = 1.0f / step_length; - - int i_dst = 1; - /* Store the length at the previous point in a variable so it can start out at zero - * (the lengths array doesn't contain 0 for the first point). */ - float prev_length = 0.0f; - for (const int i_src : IndexRange(points_num - 1)) { - const float next_length = lengths[i_src]; - const float segment_length = next_length - prev_length; - if (segment_length == 0.0f) { - continue; - } - /* Add every sample that fits in this segment. */ - const float segment_length_inv = 1.0f / segment_length; - const int segment_samples_num = std::ceil(next_length * step_length_inv - i_dst); - indices.slice(i_dst, segment_samples_num).fill(i_src); - - for (const int i : IndexRange(i_dst, segment_samples_num)) { - const float length_in_segment = step_length * i - prev_length; - factors[i] = length_in_segment * segment_length_inv; - } - - i_dst += segment_samples_num; - - prev_length = next_length; - } - - /* Add the samples on the last cyclic segment if necessary, and also the samples - * that weren't created in the previous loop due to floating point inaccuracy. */ - if (cyclic && lengths.size() > 1) { - indices.drop_front(i_dst).fill(points_num - 1); - const float segment_length = lengths.last() - lengths.last(1); - if (segment_length == 0.0f) { - return; - } - const float segment_length_inv = 1.0f / segment_length; - for (const int i : indices.index_range().drop_front(i_dst)) { - const float length_in_segment = step_length * i - prev_length; - factors[i] = length_in_segment * segment_length_inv; + const float step_length = total_length / (count - include_last_point); + threading::parallel_for(IndexRange(count), 512, [&](const IndexRange range) { + SampleSegmentHint hint; + for (const int i : range) { + /* Use minimum to avoid issues with floating point accuracy. */ + const float sample_length = std::min(total_length, i * step_length); + sample_at_length(lengths, sample_length, r_segment_indices[i], r_factors[i], &hint); } - } - else { - indices.drop_front(i_dst).fill(points_num - 2); - factors.drop_front(i_dst).fill(1.0f); - } + }); } -void create_samples_from_sorted_lengths(const Span lengths, - const Span sample_lengths, - const bool cyclic, - MutableSpan indices, - MutableSpan factors) +void sample_at_lengths(const Span accumulated_segment_lengths, + const Span sample_lengths, + MutableSpan r_segment_indices, + MutableSpan r_factors) { - BLI_assert(std::is_sorted(lengths.begin(), lengths.end())); + BLI_assert( + std::is_sorted(accumulated_segment_lengths.begin(), accumulated_segment_lengths.end())); BLI_assert(std::is_sorted(sample_lengths.begin(), sample_lengths.end())); - BLI_assert(indices.size() == sample_lengths.size()); - BLI_assert(indices.size() == factors.size()); - const int segments_num = lengths.size(); - const int points_num = cyclic ? segments_num : segments_num + 1; - const float total_length = lengths.last(); - if (total_length == 0.0f) { - indices.fill(0); - factors.fill(0.0f); - return; - } + const int count = sample_lengths.size(); + BLI_assert(count == r_segment_indices.size()); + BLI_assert(count == r_factors.size()); - int i_dst = 0; - /* Store the length at the previous point in a variable so it can start out at zero - * (the lengths array doesn't contain 0 for the first point). */ - float prev_length = 0.0f; - for (const int i_src : IndexRange(points_num - 1)) { - const float next_length = lengths[i_src]; - const float segment_length = next_length - prev_length; - if (segment_length == 0.0f) { - continue; - } - /* Add every sample that fits in this segment. It's also necessary to check if the last sample - * has been reached, since there is no upper bound on the number of samples in each segment. */ - const float segment_length_inv = 1.0f / segment_length; - while (i_dst < sample_lengths.size() && sample_lengths[i_dst] < next_length) { - const float length_in_segment = sample_lengths[i_dst] - prev_length; - const float factor = length_in_segment * segment_length_inv; - indices[i_dst] = i_src; - factors[i_dst] = factor; - i_dst++; + threading::parallel_for(IndexRange(count), 512, [&](const IndexRange range) { + SampleSegmentHint hint; + for (const int i : range) { + const float sample_length = sample_lengths[i]; + sample_at_length( + accumulated_segment_lengths, sample_length, r_segment_indices[i], r_factors[i], &hint); } - - prev_length = next_length; - } - - /* Add the samples on the last cyclic segment if necessary, and also the samples - * that weren't created in the previous loop due to floating point inaccuracy. */ - if (cyclic && lengths.size() > 1) { - const float segment_length = lengths.last() - lengths.last(1); - while (sample_lengths[i_dst] < total_length) { - const float length_in_segment = sample_lengths[i_dst] - prev_length; - const float factor = length_in_segment / segment_length; - indices[i_dst] = points_num - 1; - factors[i_dst] = factor; - i_dst++; - } - indices.drop_front(i_dst).fill(points_num - 1); - factors.drop_front(i_dst).fill(1.0f); - } - else { - indices.drop_front(i_dst).fill(points_num - 2); - factors.drop_front(i_dst).fill(1.0f); - } + }); } } // namespace blender::length_parameterize diff --git a/source/blender/blenlib/tests/BLI_length_parameterize_test.cc b/source/blender/blenlib/tests/BLI_length_parameterize_test.cc index b63e3a0ec86..11f4997f563 100644 --- a/source/blender/blenlib/tests/BLI_length_parameterize_test.cc +++ b/source/blender/blenlib/tests/BLI_length_parameterize_test.cc @@ -10,7 +10,7 @@ namespace blender::length_parameterize::tests { template Array calculate_lengths(const Span values, const bool cyclic) { - Array lengths(lengths_num(values.size(), cyclic)); + Array lengths(segments_num(values.size(), cyclic)); accumulate_lengths(values, cyclic, lengths); return lengths; } @@ -30,7 +30,7 @@ TEST(length_parameterize, FloatSimple) Array indices(4); Array factors(4); - create_uniform_samples(lengths, false, indices, factors); + sample_uniform(lengths, true, indices, factors); Array results(4); linear_interpolation(values, indices, factors, results); Array expected({ @@ -52,7 +52,7 @@ TEST(length_parameterize, Float) Array indices(20); Array factors(20); - create_uniform_samples(lengths, false, indices, factors); + sample_uniform(lengths, true, indices, factors); Array results(20); linear_interpolation(values, indices, factors, results); Array expected({ @@ -73,7 +73,7 @@ TEST(length_parameterize, Float2) Array indices(12); Array factors(12); - create_uniform_samples(lengths, false, indices, factors); + sample_uniform(lengths, true, indices, factors); Array results(12); linear_interpolation(values, indices, factors, results); Array expected({ @@ -103,7 +103,7 @@ TEST(length_parameterize, Float2Cyclic) Array indices(12); Array factors(12); - create_uniform_samples(lengths, true, indices, factors); + sample_uniform(lengths, false, indices, factors); Array results(12); linear_interpolation(values, indices, factors, results); Array expected({ @@ -133,7 +133,7 @@ TEST(length_parameterize, LineMany) Array indices(5007); Array factors(5007); - create_uniform_samples(lengths, false, indices, factors); + sample_uniform(lengths, true, indices, factors); Array results(5007); linear_interpolation(values, indices, factors, results); Array expected({ @@ -152,7 +152,7 @@ TEST(length_parameterize, CyclicMany) Array indices(5007); Array factors(5007); - create_uniform_samples(lengths, true, indices, factors); + sample_uniform(lengths, false, indices, factors); Array results(5007); linear_interpolation(values, indices, factors, results); Array expected({ @@ -176,7 +176,7 @@ TEST(length_parameterize, InterpolateColor) Array indices(10); Array factors(10); - create_uniform_samples(lengths, true, indices, factors); + sample_uniform(lengths, false, indices, factors); Array results(10); linear_interpolation(colors, indices, factors, results); Array expected({ @@ -207,7 +207,7 @@ TEST(length_parameterize, ArbitraryFloatSimple) Array sample_lengths{{0.5f, 1.5f, 2.0f, 4.0f}}; Array indices(4); Array factors(4); - create_samples_from_sorted_lengths(lengths, sample_lengths, false, indices, factors); + sample_at_lengths(lengths, sample_lengths, indices, factors); Array results(4); linear_interpolation(values, indices, factors, results); results.as_span().print_as_lines("results"); @@ -231,7 +231,7 @@ TEST(length_parameterize, ArbitraryFloat2) {0.5f, 1.5f, 2.0f, 2.0f, 2.1f, 2.5f, 3.5f, 3.6f, 3.8f, 3.85f, 3.90f, 4.0f}}; Array indices(12); Array factors(12); - create_samples_from_sorted_lengths(lengths, sample_lengths, true, indices, factors); + sample_at_lengths(lengths, sample_lengths, indices, factors); Array results(12); linear_interpolation(values, indices, factors, results); results.as_span().print_as_lines("results"); diff --git a/source/blender/editors/sculpt_paint/curves_sculpt_brush.cc b/source/blender/editors/sculpt_paint/curves_sculpt_brush.cc index 1c785fa6452..7d17db515fb 100644 --- a/source/blender/editors/sculpt_paint/curves_sculpt_brush.cc +++ b/source/blender/editors/sculpt_paint/curves_sculpt_brush.cc @@ -345,7 +345,7 @@ void move_last_point_and_resample(MutableSpan positions, const float3 &n { /* Find the accumulated length of each point in the original curve, * treating it as a poly curve for performance reasons and simplicity. */ - Array orig_lengths(length_parameterize::lengths_num(positions.size(), false)); + Array orig_lengths(length_parameterize::segments_num(positions.size(), false)); length_parameterize::accumulate_lengths(positions, false, orig_lengths); const float orig_total_length = orig_lengths.last(); @@ -363,8 +363,7 @@ void move_last_point_and_resample(MutableSpan positions, const float3 &n Array indices(positions.size() - 1); Array factors(positions.size() - 1); - length_parameterize::create_samples_from_sorted_lengths( - orig_lengths, new_lengths, false, indices, factors); + length_parameterize::sample_at_lengths(orig_lengths, new_lengths, indices, factors); Array new_positions(positions.size() - 1); length_parameterize::linear_interpolation(positions, indices, factors, new_positions); diff --git a/source/blender/geometry/intern/resample_curves.cc b/source/blender/geometry/intern/resample_curves.cc index c18c776fead..dd1da62408c 100644 --- a/source/blender/geometry/intern/resample_curves.cc +++ b/source/blender/geometry/intern/resample_curves.cc @@ -234,11 +234,10 @@ static Curves *resample_to_uniform(const CurveComponent &src_component, 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)); + length_parameterize::sample_uniform(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 -- cgit v1.2.3