[Bf-blender-cvs] [12bf0af064e] temp-geometry-nodes-curve-deform-node: Curve Deform Node: Refactor parameter sorting again
Hans Goudey
noreply at git.blender.org
Thu Jun 10 16:07:08 CEST 2021
Commit: 12bf0af064e8bfb4f36d4f58c3c2aa43139d65d1
Author: Hans Goudey
Date: Wed Jun 9 19:54:49 2021 -0500
Branches: temp-geometry-nodes-curve-deform-node
https://developer.blender.org/rB12bf0af064e8bfb4f36d4f58c3c2aa43139d65d1
Curve Deform Node: Refactor parameter sorting again
===================================================================
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/intern/spline_base.cc b/source/blender/blenkernel/intern/spline_base.cc
index 31dbb940617..4b84f55851b 100644
--- a/source/blender/blenkernel/intern/spline_base.cc
+++ b/source/blender/blenkernel/intern/spline_base.cc
@@ -319,13 +319,22 @@ Array<float> Spline::sample_uniform_index_factors(const int samples_size) const
return samples;
}
+static void assert_sorted_array_in_range(Span<float> data, const float min, const float max)
+{
+ BLI_assert(data.first() >= min);
+ for (const int i : IndexRange(1, data.size() - 1)) {
+ BLI_assert(data[i] >= data[i - 1]);
+ }
+ BLI_assert(data.last() <= max);
+}
+
/**
- * Transform an array of unsorted length parameters into index factors. The samples are indices
- * and factors to the next index encoded in floats. The logic for converting from the float values
- * to interpolation data is in #lookup_data_from_index_factor.
+ * Transform an array of sorted length parameters into index factors. The result is indices
+ * and factors to the next index, encoded in floats. The logic for converting from the float
+ * values to interpolation data is in #lookup_data_from_index_factor.
*
- * \param parameters: Lengths along the spline to be transformed into index factors.
- * Must be between 0 and the total length of the spline.
+ * \param parameters: Lengths along the spline to be transformed into index factors
+ * (to save another allocation). Must be between zero 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.
@@ -333,26 +342,14 @@ Array<float> Spline::sample_uniform_index_factors(const int samples_size) const
void Spline::sample_length_parameters_to_index_factors(MutableSpan<float> parameters) const
{
const Span<float> lengths = this->evaluated_lengths();
-
- /* 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());
+ assert_sorted_array_in_range(parameters, 0.0f, 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 parameter_index : sorted_indices) {
- const float sample_length = parameters[parameter_index];
+ for (const int i_sample : parameters.index_range()) {
+ const float sample_length = parameters[i_sample];
/* Skip over every evaluated point that fits before this sample. */
while (lengths[i_evaluated] < sample_length) {
@@ -361,7 +358,7 @@ void Spline::sample_length_parameters_to_index_factors(MutableSpan<float> parame
}
const float factor = (sample_length - prev_length) / (lengths[i_evaluated] - prev_length);
- parameters[parameter_index] = i_evaluated + factor;
+ parameters[i_sample] = 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 8f57ef2d64a..30cbf0c5ea8 100644
--- a/source/blender/nodes/geometry/nodes/node_geo_curve_deform.cc
+++ b/source/blender/nodes/geometry/nodes/node_geo_curve_deform.cc
@@ -92,6 +92,7 @@ static void geo_node_curve_deform_update(bNodeTree *UNUSED(ntree), bNode *node)
static void spline_deform(const Spline &spline,
Span<float> index_factors,
+ Span<int> sorted_indices,
const int axis_index,
MutableSpan<float3> positions)
{
@@ -102,6 +103,7 @@ static void spline_deform(const Spline &spline,
parallel_for(positions.index_range(), 1024, [&](IndexRange range) {
for (const int i : range) {
+ const int i_position = sorted_indices[i];
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;
@@ -115,11 +117,11 @@ static void spline_deform(const Spline &spline,
.normalized());
matrix.apply_scale(interpf(radii[next_index], radii[index], factor));
- float3 position = positions[i];
+ float3 position = positions[i_position];
position[axis_index] = 0.0f;
- positions[i] = matrix * position;
- positions[i] += float3::interpolate(
+ positions[i_position] = matrix * position;
+ positions[i_position] += float3::interpolate(
spline_positions[index], spline_positions[next_index], factor);
}
});
@@ -203,40 +205,50 @@ 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();
+ /* #sample_length_parameters_to_index_factors requires an array of sorted parameters.
+ * Sort indices based on the parameters before processing, build the parameters final
+ * parameters, then use the indices to map back to the orignal positions. */
Array<float> parameters(size);
+ Array<int> sorted_indices(size);
+ for (const int i : sorted_indices.index_range()) {
+ sorted_indices[i] = i;
+ }
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);
- }
+ std::sort(sorted_indices.begin(), sorted_indices.end(), [&](const int &a, const int &b) {
+ return positions[a][axis_index] > positions[b][axis_index];
});
+ for (const int i : IndexRange(size)) {
+ parameters[i] = total_length -
+ std::clamp(positions[sorted_indices[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);
- }
+ std::sort(sorted_indices.begin(), sorted_indices.end(), [&](const int &a, const int &b) {
+ return positions[a][axis_index] < positions[b][axis_index];
});
+ for (const int i : IndexRange(size)) {
+ parameters[i] = std::clamp(positions[sorted_indices[i]][axis_index], 0.0f, total_length);
+ }
}
}
else {
BLI_assert(mode == GEO_NODE_CURVE_DEFORM_ATTRIBUTE);
- GVArrayPtr attribute = params.get_input_attribute(
- "Factor", component, ATTR_DOMAIN_POINT, CD_PROP_FLOAT, nullptr);
- if (!attribute) {
- return;
- }
+ GVArray_Typed<float> attribute = params.get_input_attribute<float>(
+ "Factor", component, ATTR_DOMAIN_POINT, 0.0f);
+
+ std::sort(sorted_indices.begin(), sorted_indices.end(), [&](const int &a, const int &b) {
+ return attribute[a] < attribute[b];
+ });
- GVArray_Typed<float> parameter_attribute{*attribute};
for (const int i : IndexRange(size)) {
- parameters[i] = std::clamp(parameter_attribute[i], 0.0f, total_length);
+ parameters[i] = std::clamp(attribute[sorted_indices[i]] * total_length, 0.0f, total_length);
}
}
spline.sample_length_parameters_to_index_factors(parameters);
- spline_deform(spline, parameters, axis_index, positions);
+ spline_deform(spline, parameters, sorted_indices, axis_index, positions);
position_attribute.save();
}
More information about the Bf-blender-cvs
mailing list