diff options
Diffstat (limited to 'source/blender')
4 files changed, 166 insertions, 34 deletions
diff --git a/source/blender/blenlib/BLI_length_parameterize.hh b/source/blender/blenlib/BLI_length_parameterize.hh index e4a4e9cbb9c..6fe1c6513a2 100644 --- a/source/blender/blenlib/BLI_length_parameterize.hh +++ b/source/blender/blenlib/BLI_length_parameterize.hh @@ -77,4 +77,22 @@ void create_uniform_samples(Span<float> lengths, MutableSpan<int> indices, MutableSpan<float> 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 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 #lenghts 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. + */ +void create_samples_from_sorted_lengths(Span<float> lengths, + Span<float> sample_lengths, + bool cyclic, + MutableSpan<int> indices, + MutableSpan<float> factors); + } // namespace blender::length_parameterize diff --git a/source/blender/blenlib/intern/length_parameterize.cc b/source/blender/blenlib/intern/length_parameterize.cc index d6862b96944..7c0fc860b53 100644 --- a/source/blender/blenlib/intern/length_parameterize.cc +++ b/source/blender/blenlib/intern/length_parameterize.cc @@ -77,4 +77,68 @@ void create_uniform_samples(const Span<float> lengths, } } +void create_samples_from_sorted_lengths(const Span<float> lengths, + const Span<float> sample_lengths, + const bool cyclic, + MutableSpan<int> indices, + MutableSpan<float> factors) +{ + BLI_assert(std::is_sorted(lengths.begin(), 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; + } + + 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++; + } + + 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 4a8b7095888..b63e3a0ec86 100644 --- a/source/blender/blenlib/tests/BLI_length_parameterize_test.cc +++ b/source/blender/blenlib/tests/BLI_length_parameterize_test.cc @@ -199,4 +199,60 @@ TEST(length_parameterize, InterpolateColor) } } +TEST(length_parameterize, ArbitraryFloatSimple) +{ + Array<float> values{{0, 1, 4}}; + Array<float> lengths = calculate_lengths(values.as_span(), false); + + Array<float> sample_lengths{{0.5f, 1.5f, 2.0f, 4.0f}}; + Array<int> indices(4); + Array<float> factors(4); + create_samples_from_sorted_lengths(lengths, sample_lengths, false, indices, factors); + Array<float> results(4); + linear_interpolation<float>(values, indices, factors, results); + results.as_span().print_as_lines("results"); + Array<float> expected({ + 0.5f, + 1.5f, + 2.0f, + 4.0f, + }); + for (const int i : results.index_range()) { + EXPECT_NEAR(results[i], expected[i], 1e-5); + } +} + +TEST(length_parameterize, ArbitraryFloat2) +{ + Array<float2> values{{{0, 0}, {1, 0}, {1, 1}, {0, 1}}}; + Array<float> lengths = calculate_lengths(values.as_span(), true); + + Array<float> sample_lengths{ + {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<int> indices(12); + Array<float> factors(12); + create_samples_from_sorted_lengths(lengths, sample_lengths, true, indices, factors); + Array<float2> results(12); + linear_interpolation<float2>(values, indices, factors, results); + results.as_span().print_as_lines("results"); + Array<float2> expected({ + {0.5f, 0.0f}, + {1.0f, 0.5f}, + {1.0f, 1.0f}, + {1.0f, 1.0f}, + {0.9f, 1.0f}, + {0.5f, 1.0f}, + {0.0f, 0.5f}, + {0.0f, 0.4f}, + {0.0f, 0.2f}, + {0.0f, 0.15f}, + {0.0f, 0.1f}, + {0.0f, 0.0f}, + }); + for (const int i : results.index_range()) { + EXPECT_NEAR(results[i].x, expected[i].x, 1e-5); + EXPECT_NEAR(results[i].y, expected[i].y, 1e-5); + } +} + } // namespace blender::length_parameterize::tests diff --git a/source/blender/editors/sculpt_paint/curves_sculpt_snake_hook.cc b/source/blender/editors/sculpt_paint/curves_sculpt_snake_hook.cc index 39321243553..b367c5bb6ec 100644 --- a/source/blender/editors/sculpt_paint/curves_sculpt_snake_hook.cc +++ b/source/blender/editors/sculpt_paint/curves_sculpt_snake_hook.cc @@ -7,6 +7,7 @@ #include "BLI_float4x4.hh" #include "BLI_index_mask_ops.hh" #include "BLI_kdtree.h" +#include "BLI_length_parameterize.hh" #include "BLI_rand.hh" #include "BLI_vector.hh" @@ -232,43 +233,36 @@ struct SnakeHookOperatorExecutor { }); } - void move_last_point_and_resample(MutableSpan<float3> positions_cu, - const float3 &new_last_point_position_cu) const + void move_last_point_and_resample(MutableSpan<float3> positions, + const float3 &new_last_position) const { - Vector<float> old_lengths_cu; - old_lengths_cu.append(0.0f); - /* Used to (1) normalize the segment sizes over time and (2) support making zero-length - * segments */ - const float extra_length = 0.001f; - for (const int segment_i : IndexRange(positions_cu.size() - 1)) { - const float3 &p1_cu = positions_cu[segment_i]; - const float3 &p2_cu = positions_cu[segment_i + 1]; - const float length_cu = math::distance(p1_cu, p2_cu); - old_lengths_cu.append(old_lengths_cu.last() + length_cu + extra_length); - } - Vector<float> point_factors; - for (float &old_length_cu : old_lengths_cu) { - point_factors.append(old_length_cu / old_lengths_cu.last()); + /* Find the accumulated length of each point in the original curve, + * treating it as a poly curve for performance reasons and simplicity. */ + Array<float> orig_lengths(length_parameterize::lengths_num(positions.size(), false)); + length_parameterize::accumulate_lengths<float3>(positions, false, orig_lengths); + const float orig_total_length = orig_lengths.last(); + + /* Find the factor by which the new curve is shorter or longer than the original. */ + const float new_last_segment_length = math::distance(positions.last(1), new_last_position); + const float new_total_length = orig_lengths.last(1) + new_last_segment_length; + const float length_factor = new_total_length / orig_total_length; + + /* Calculate the lengths to sample the original curve with by scaling the original lengths. */ + Array<float> new_lengths(positions.size() - 1); + new_lengths.first() = 0.0f; + for (const int i : new_lengths.index_range().drop_front(1)) { + new_lengths[i] = orig_lengths[i - 1] * length_factor; } - PolySpline new_spline; - new_spline.resize(positions_cu.size()); - MutableSpan<float3> new_spline_positions_cu = new_spline.positions(); - for (const int i : IndexRange(positions_cu.size() - 1)) { - new_spline_positions_cu[i] = positions_cu[i]; - } - new_spline_positions_cu.last() = new_last_point_position_cu; - new_spline.mark_cache_invalid(); - - for (const int i : positions_cu.index_range()) { - const float factor = point_factors[i]; - const Spline::LookupResult lookup = new_spline.lookup_evaluated_factor(factor); - const float index_factor = lookup.evaluated_index + lookup.factor; - float3 p_cu; - new_spline.sample_with_index_factors<float3>( - new_spline_positions_cu, {&index_factor, 1}, {&p_cu, 1}); - positions_cu[i] = p_cu; - } + Array<int> indices(positions.size() - 1); + Array<float> factors(positions.size() - 1); + length_parameterize::create_samples_from_sorted_lengths( + orig_lengths, new_lengths, false, indices, factors); + + Array<float3> new_positions(positions.size() - 1); + length_parameterize::linear_interpolation<float3>(positions, indices, factors, new_positions); + positions.drop_back(1).copy_from(new_positions); + positions.last() = new_last_position; } }; |