[Bf-blender-cvs] [4602874a047] temp-geometry-nodes-curve-deform-node: Curve Deform: Simplify parameter calculation, add comments
Hans Goudey
noreply at git.blender.org
Tue Jun 8 06:48:29 CEST 2021
Commit: 4602874a04705bc2424791255e47ea8f60307d20
Author: Hans Goudey
Date: Mon Jun 7 23:48:21 2021 -0500
Branches: temp-geometry-nodes-curve-deform-node
https://developer.blender.org/rB4602874a04705bc2424791255e47ea8f60307d20
Curve Deform: Simplify parameter calculation, add comments
===================================================================
M source/blender/blenkernel/BKE_spline.hh
M source/blender/blenkernel/intern/spline_base.cc
M source/blender/nodes/geometry/nodes/node_geo_curve_deform.cc
===================================================================
diff --git a/source/blender/blenkernel/BKE_spline.hh b/source/blender/blenkernel/BKE_spline.hh
index 92aa9313ef7..bae44f19952 100644
--- a/source/blender/blenkernel/BKE_spline.hh
+++ b/source/blender/blenkernel/BKE_spline.hh
@@ -171,13 +171,7 @@ class Spline {
blender::Array<float> sample_uniform_index_factors(const int samples_size) const;
- struct Parameter {
- /* Used as an "index factor" after the function. */
- float length;
- int data_index;
- };
- void sample_parameters_to_index_factors(
- blender::MutableSpan<Parameter> sample_index_factors) const;
+ void sample_length_parameters_to_index_factors(blender::MutableSpan<float> parameters) const;
LookupResult lookup_data_from_index_factor(const float index_factor) const;
diff --git a/source/blender/blenkernel/intern/spline_base.cc b/source/blender/blenkernel/intern/spline_base.cc
index 45238c2a45b..8d3e1a62d25 100644
--- a/source/blender/blenkernel/intern/spline_base.cc
+++ b/source/blender/blenkernel/intern/spline_base.cc
@@ -313,29 +313,40 @@ Array<float> Spline::sample_uniform_index_factors(const int samples_size) const
return samples;
}
-void Spline::sample_parameters_to_index_factors(MutableSpan<Parameter> sample_index_factors) const
+/**
+ * Transform an array of unsorted length parameters into index factors (integer part the segment
+ * index, float part the factor), which can be used for retrieving evaluated values from the curve
+ * at specific points.
+ *
+ * \param parameters: Lengths along the spline to be transformed into index factors.
+ * Must be between 0 and the total length of the spline.
+ *
+ * \note The implementation is similar to #sample_uniform_index_factors(), though
+ * the two loops are inverted, and obviously custom parameters are provided.
+ */
+void Spline::sample_length_parameters_to_index_factors(MutableSpan<float> parameters) const
{
const Span<float> lengths = this->evaluated_lengths();
- const float total_length = this->length();
- {
- float last = 0.0f;
- for (const Spline::Parameter ¶meter : sample_index_factors) {
- /* Parameters must be provided in increasing order. */
- BLI_assert(parameter.length >= last);
- last = parameter.length;
- }
- /* Parameters must be in the 0-total_length range. */
- BLI_assert(last <= total_length);
- BLI_assert(sample_index_factors.first().length >= 0.0f);
+ /* In order to quickly loop through the evaluated lengths to find the index factors, access the
+ * incoming parameters via an array of sorted indices. Knowing the order significantly speeds up
+ * finding the results, since we can avoid doing a separate binary search for every parameter. */
+ Array<int> sorted_indices(parameters.size());
+ for (const int i : sorted_indices.index_range()) {
+ sorted_indices[i] = i;
}
+ std::sort(sorted_indices.begin(), sorted_indices.end(), [&](const int &a, const int &b) {
+ return parameters[a] < parameters[b];
+ });
+ BLI_assert(parameters[sorted_indices[0] >= 0.0f]);
+ BLI_assert(parameters[sorted_indices.last()] <= this->length());
/* Store the length at the previous evaluated 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;
int i_evaluated = 0;
- for (const int i_sample : sample_index_factors.index_range()) {
- const float sample_length = sample_index_factors[i_sample].length;
+ for (const int parameter_index : sorted_indices) {
+ const float sample_length = parameters[parameter_index];
/* Skip over every evaluated point that fits before this sample. */
while (lengths[i_evaluated] < sample_length) {
@@ -344,7 +355,7 @@ void Spline::sample_parameters_to_index_factors(MutableSpan<Parameter> sample_in
}
const float factor = (sample_length - prev_length) / (lengths[i_evaluated] - prev_length);
- sample_index_factors[i_sample].length = i_evaluated + factor;
+ parameters[parameter_index] = i_evaluated + factor;
}
}
diff --git a/source/blender/nodes/geometry/nodes/node_geo_curve_deform.cc b/source/blender/nodes/geometry/nodes/node_geo_curve_deform.cc
index 4e73e767f6b..0f7f85756f5 100644
--- a/source/blender/nodes/geometry/nodes/node_geo_curve_deform.cc
+++ b/source/blender/nodes/geometry/nodes/node_geo_curve_deform.cc
@@ -92,7 +92,7 @@ static void geo_node_curve_deform_update(bNodeTree *UNUSED(ntree), bNode *node)
}
static void spline_deform(const Spline &spline,
- Span<Spline::Parameter> index_factors,
+ Span<float> index_factors,
const int axis_index,
MutableSpan<float3> positions)
{
@@ -103,12 +103,8 @@ static void spline_deform(const Spline &spline,
parallel_for(positions.index_range(), 1024, [&](IndexRange range) {
for (const int i : range) {
- const int i_position = index_factors[i].data_index;
- float3 position = positions[i_position];
- position[axis_index] = 0.0f;
- const Spline::LookupResult interp = spline.lookup_data_from_index_factor(
- index_factors[i].length);
+ const Spline::LookupResult interp = spline.lookup_data_from_index_factor(index_factors[i]);
const int index = interp.evaluated_index;
const int next_index = interp.next_evaluated_index;
const float factor = interp.factor;
@@ -121,8 +117,11 @@ static void spline_deform(const Spline &spline,
.normalized());
matrix.apply_scale(interpf(radii[next_index], radii[index], factor));
- positions[i_position] = matrix * position;
- positions[i_position] += float3::interpolate(
+ float3 position = positions[i];
+ position[axis_index] = 0.0f;
+
+ positions[i] = matrix * position;
+ positions[i] += float3::interpolate(
spline_positions[index], spline_positions[next_index], factor);
}
});
@@ -206,30 +205,23 @@ static void execute_on_component(const GeoNodeExecParams ¶ms,
component.attribute_try_get_for_output<float3>("position", ATTR_DOMAIN_POINT, {0, 0, 0});
MutableSpan<float3> positions = position_attribute.as_span();
- Array<Spline::Parameter> parameters(size);
+ Array<float> parameters(size);
if (mode == GEO_NODE_CURVE_DEFORM_POSITION) {
if (axis_is_negative(axis)) {
parallel_for(positions.index_range(), 4096, [&](IndexRange range) {
for (const int i : range) {
- parameters[i] = {std::clamp(positions[i][axis_index], 0.0f, total_length), i};
+ parameters[i] = std::clamp(positions[i][axis_index], 0.0f, total_length);
}
});
}
else {
parallel_for(positions.index_range(), 4096, [&](IndexRange range) {
for (const int i : range) {
- parameters[i] = {total_length - std::clamp(positions[i][axis_index], 0.0f, total_length),
- i};
+ parameters[i] = total_length - std::clamp(positions[i][axis_index], 0.0f, total_length);
}
});
}
-
- std::sort(parameters.begin(),
- parameters.end(),
- [](const Spline::Parameter &a, const Spline::Parameter &b) {
- return a.length < b.length;
- });
}
else {
BLI_assert(mode == GEO_NODE_CURVE_DEFORM_ATTRIBUTE);
@@ -241,11 +233,11 @@ static void execute_on_component(const GeoNodeExecParams ¶ms,
GVArray_Typed<float> parameter_attribute{*attribute};
for (const int i : IndexRange(size)) {
- parameters[i] = {std::clamp(parameter_attribute[i], 0.0f, total_length), i};
+ parameters[i] = std::clamp(parameter_attribute[i], 0.0f, total_length);
}
}
- spline.sample_parameters_to_index_factors(parameters);
+ spline.sample_length_parameters_to_index_factors(parameters);
spline_deform(spline, parameters, axis_index, positions);
position_attribute.save();
More information about the Bf-blender-cvs
mailing list