From 215f805ce6b540177dedd71721e62c56a764a5ea Mon Sep 17 00:00:00 2001 From: Hans Goudey Date: Tue, 19 Jul 2022 21:48:32 -0500 Subject: Curves: Remove use of CurveEval in sculpt brushes This commit removes the use of PolySpline for resampling curves and replaces it with the length parameterization utility for that purpose. I didn't test performance, but I would expect the shrinking to be slightly faster because I reused some arrays to avoid allocating them for every curve. I noted some potential improvements in the "add curves" function. Differential Revision: https://developer.blender.org/D15342 --- .../sculpt_paint/curves_sculpt_grow_shrink.cc | 73 ++++++++++++---------- .../blender/geometry/intern/add_curves_on_mesh.cc | 67 ++++++++++++-------- 2 files changed, 80 insertions(+), 60 deletions(-) (limited to 'source') diff --git a/source/blender/editors/sculpt_paint/curves_sculpt_grow_shrink.cc b/source/blender/editors/sculpt_paint/curves_sculpt_grow_shrink.cc index 709ecc79967..408139d6653 100644 --- a/source/blender/editors/sculpt_paint/curves_sculpt_grow_shrink.cc +++ b/source/blender/editors/sculpt_paint/curves_sculpt_grow_shrink.cc @@ -4,8 +4,7 @@ #include "BLI_enumerable_thread_specific.hh" #include "BLI_float4x4.hh" -#include "BLI_kdtree.h" -#include "BLI_rand.hh" +#include "BLI_length_parameterize.hh" #include "BLI_vector.hh" #include "PIL_time.h" @@ -14,19 +13,13 @@ #include "BKE_attribute_math.hh" #include "BKE_brush.h" -#include "BKE_bvhutils.h" #include "BKE_context.h" #include "BKE_curves.hh" -#include "BKE_mesh.h" -#include "BKE_mesh_runtime.h" #include "BKE_paint.h" -#include "BKE_spline.hh" #include "DNA_brush_enums.h" #include "DNA_brush_types.h" #include "DNA_curves_types.h" -#include "DNA_mesh_types.h" -#include "DNA_meshdata_types.h" #include "DNA_object_types.h" #include "DNA_screen_types.h" #include "DNA_space_types.h" @@ -70,6 +63,24 @@ class ShrinkCurvesEffect : public CurvesEffect { private: const Brush &brush_; + /** Storage of per-curve parameterization data to avoid reallocation. */ + struct ParameterizationBuffers { + Array old_positions; + Array old_lengths; + Array sample_lengths; + Array indices; + Array factors; + + void reinitialize(const int points_num) + { + this->old_positions.reinitialize(points_num); + this->old_lengths.reinitialize(length_parameterize::segments_num(points_num, false)); + this->sample_lengths.reinitialize(points_num); + this->indices.reinitialize(points_num); + this->factors.reinitialize(points_num); + } + }; + public: ShrinkCurvesEffect(const Brush &brush) : brush_(brush) { @@ -81,46 +92,42 @@ class ShrinkCurvesEffect : public CurvesEffect { { MutableSpan positions_cu = curves.positions_for_write(); threading::parallel_for(curve_indices.index_range(), 256, [&](const IndexRange range) { + ParameterizationBuffers data; for (const int influence_i : range) { const int curve_i = curve_indices[influence_i]; const float move_distance_cu = move_distances_cu[influence_i]; - const IndexRange curve_points = curves.points_for_curve(curve_i); - this->shrink_curve(positions_cu, curve_points, move_distance_cu); + const IndexRange points = curves.points_for_curve(curve_i); + this->shrink_curve(positions_cu.slice(points), move_distance_cu, data); } }); } + private: void shrink_curve(MutableSpan positions, - const IndexRange curve_points, - const float shrink_length) const + const float shrink_length, + ParameterizationBuffers &data) const { - PolySpline spline; - spline.resize(curve_points.size()); - MutableSpan spline_positions = spline.positions(); - spline_positions.copy_from(positions.slice(curve_points)); - spline.mark_cache_invalid(); + namespace lp = length_parameterize; + data.reinitialize(positions.size()); + + /* Copy the old positions to facilitate mixing from neighbors for the resulting curve. */ + data.old_positions.as_mutable_span().copy_from(positions); + + lp::accumulate_lengths(data.old_positions, false, data.old_lengths); + const float min_length = brush_.curves_sculpt_settings->minimum_length; - const float old_length = spline.length(); + const float old_length = data.old_lengths.last(); const float new_length = std::max(min_length, old_length - shrink_length); const float length_factor = std::clamp(new_length / old_length, 0.0f, 1.0f); - Vector old_point_lengths; - old_point_lengths.append(0.0f); - for (const int i : spline_positions.index_range().drop_back(1)) { - const float3 &p1 = spline_positions[i]; - const float3 &p2 = spline_positions[i + 1]; - const float length = math::distance(p1, p2); - old_point_lengths.append(old_point_lengths.last() + length); + data.sample_lengths.first() = 0.0f; + for (const int i : data.old_lengths.index_range()) { + data.sample_lengths[i + 1] = data.old_lengths[i] * length_factor; } - for (const int i : spline_positions.index_range()) { - const float eval_length = old_point_lengths[i] * length_factor; - const Spline::LookupResult lookup = spline.lookup_evaluated_length(eval_length); - const float index_factor = lookup.evaluated_index + lookup.factor; - float3 p; - spline.sample_with_index_factors(spline_positions, {&index_factor, 1}, {&p, 1}); - positions[curve_points[i]] = p; - } + lp::sample_at_lengths(data.old_lengths, data.sample_lengths, data.indices, data.factors); + + lp::linear_interpolation(data.old_positions, data.indices, data.factors, positions); } }; diff --git a/source/blender/geometry/intern/add_curves_on_mesh.cc b/source/blender/geometry/intern/add_curves_on_mesh.cc index 34551bd474f..a69073af207 100644 --- a/source/blender/geometry/intern/add_curves_on_mesh.cc +++ b/source/blender/geometry/intern/add_curves_on_mesh.cc @@ -1,7 +1,9 @@ /* SPDX-License-Identifier: GPL-2.0-or-later */ +#include "BLI_length_parameterize.hh" + +#include "BKE_attribute_math.hh" #include "BKE_mesh_sample.hh" -#include "BKE_spline.hh" #include "GEO_add_curves_on_mesh.hh" @@ -145,16 +147,16 @@ static void interpolate_position_with_interpolation(CurvesGeometry &curves, const int added_curves_num = root_positions_cu.size(); threading::parallel_for(IndexRange(added_curves_num), 256, [&](const IndexRange range) { - for (const int i : range) { - const NeighborCurves &neighbors = neighbors_per_curve[i]; - const int curve_i = old_curves_num + i; + for (const int added_curve_i : range) { + const NeighborCurves &neighbors = neighbors_per_curve[added_curve_i]; + const int curve_i = old_curves_num + added_curve_i; const IndexRange points = curves.points_for_curve(curve_i); - const float length_cu = new_lengths_cu[i]; - const float3 &normal_su = new_normals_su[i]; + const float length_cu = new_lengths_cu[added_curve_i]; + const float3 &normal_su = new_normals_su[added_curve_i]; const float3 normal_cu = math::normalize(surface_to_curves_normal_mat * normal_su); - const float3 &root_cu = root_positions_cu[i]; + const float3 &root_cu = root_positions_cu[added_curve_i]; if (neighbors.is_empty()) { /* If there are no neighbors, just make a straight line. */ @@ -197,30 +199,41 @@ static void interpolate_position_with_interpolation(CurvesGeometry &curves, const IndexRange neighbor_points = curves.points_for_curve(neighbor_curve_i); const float3 &neighbor_root_cu = positions_cu[neighbor_points[0]]; - /* Use a temporary #PolySpline, because that's the easiest way to resample an - * existing curve right now. Resampling is necessary if the length of the new curve - * does not match the length of the neighbors or the number of handle points is - * different. */ - PolySpline neighbor_spline; - neighbor_spline.resize(neighbor_points.size()); - neighbor_spline.positions().copy_from(positions_cu.slice(neighbor_points)); - neighbor_spline.mark_cache_invalid(); + /* Sample the positions on neighbors and mix them into the final positions of the curve. + * Resampling is necessary if the length of the new curve does not match the length of the + * neighbors or the number of handle points is different. + * + * TODO: The lengths can be cached so they aren't recomputed if a curve is a neighbor for + * multiple new curves. Also, allocations could be avoided by reusing some arrays. */ + + const Span neighbor_positions_cu = positions_cu.slice(neighbor_points); + if (neighbor_positions_cu.size() == 1) { + /* Skip interpolating positions from neighbors with only one point. */ + continue; + } + Array lengths(length_parameterize::segments_num(neighbor_points.size(), false)); + length_parameterize::accumulate_lengths(neighbor_positions_cu, false, lengths); + const float neighbor_length_cu = lengths.last(); - const float neighbor_length_cu = neighbor_spline.length(); + Array sample_lengths(points.size()); const float length_factor = std::min(1.0f, length_cu / neighbor_length_cu); - const float resample_factor = (1.0f / (points.size() - 1.0f)) * length_factor; - for (const int j : IndexRange(points.size())) { - const Spline::LookupResult lookup = neighbor_spline.lookup_evaluated_factor( - j * resample_factor); - const float index_factor = lookup.evaluated_index + lookup.factor; - float3 p; - neighbor_spline.sample_with_index_factors( - neighbor_spline.positions(), {&index_factor, 1}, {&p, 1}); - const float3 relative_coord = p - neighbor_root_cu; - float3 rotated_relative_coord = relative_coord; + for (const int i : sample_lengths.index_range()) { + sample_lengths[i] = i * resample_factor * neighbor_length_cu; + } + + Array indices(points.size()); + Array factors(points.size()); + length_parameterize::sample_at_lengths(lengths, sample_lengths, indices, factors); + + for (const int i : IndexRange(points.size())) { + const float3 sample_cu = math::interpolate(neighbor_positions_cu[indices[i]], + neighbor_positions_cu[indices[i] + 1], + factors[i]); + const float3 relative_to_root_cu = sample_cu - neighbor_root_cu; + float3 rotated_relative_coord = relative_to_root_cu; mul_m3_v3(normal_rotation_cu, rotated_relative_coord); - positions_cu[points[j]] += neighbor.weight * rotated_relative_coord; + positions_cu[points[i]] += neighbor.weight * rotated_relative_coord; } } } -- cgit v1.2.3