blender
/
blender
129
398
Fork 572
Code Issues 6.2k Pull Requests 747 Projects 19 Wiki Activity

Add a utility for sampling segment indices and factors from arbitrary 

lengths along a set of points. This can be used for the sample curves
node, or finding new points along a curve when extending
or shrinking it.

This commit uses it in the snake hook brush as an example.

The logic is similar to the uniform length sampling, but the next
sample length is retrieved from the input instead of multiplication.

For the sample node in the future, though this sort of sampling can be
potentially done more efficiently for specific curve types besides
poly curves, it's simpler, at least as a start, to work on a set of
evaluated points that can be treated like a poly curve.

Differential Revision: https://developer.blender.org/D14571
This commit is contained in:
Hans Goudey 2022-04-08 13:13:35 -05:00
parent bc9c9631a4
commit eb40b231f9
4 changed files with 165 additions and 33 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

18
source/blender/blenlib/BLI_length_parameterize.hh
View File

@ -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

64
source/blender/blenlib/intern/length_parameterize.cc
View File

@ -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

56
source/blender/blenlib/tests/BLI_length_parameterize_test.cc
View File

@ -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

60
source/blender/editors/sculpt_paint/curves_sculpt_snake_hook.cc
View File

@ -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();
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);
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<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;
}
};