[Bf-blender-cvs] [72d25fa41d8] master: Curves: Add length cache, length paramerterize utility
Hans Goudey
noreply at git.blender.org
Wed Mar 30 02:46:23 CEST 2022
Commit: 72d25fa41d8c5753e4cdc1293d407e16c1431119
Author: Hans Goudey
Date: Tue Mar 29 19:44:01 2022 -0500
Branches: master
https://developer.blender.org/rB72d25fa41d8c5753e4cdc1293d407e16c1431119
Curves: Add length cache, length paramerterize utility
This commit adds calculation of lengths along the curve for each
evaluated point. This is used for sampling, resampling, the "curve
parameter" node, and potentially more places in the future.
This commit also includes a utility for calculation of uniform samples
in blenlib. It can find evenlyspaced samples along a sequence of points
and use linear interpolation to move data from those points to the
samples. Making the utility more general aligns better with the more
functional approach of the new curves code and makes the behavior
available elsewhere.
A "color math" header is added to allow very basic interpolation
between two colors in the `blender::math` namespace.
Differential Revision: https://developer.blender.org/D14382
===================================================================
M source/blender/blenkernel/BKE_curves.hh
M source/blender/blenkernel/intern/curves_geometry.cc
A source/blender/blenlib/BLI_length_parameterize.hh
A source/blender/blenlib/BLI_math_color.hh
M source/blender/blenlib/CMakeLists.txt
A source/blender/blenlib/intern/length_parameterize.cc
A source/blender/blenlib/tests/BLI_length_parameterize_test.cc
===================================================================
diff --git a/source/blender/blenkernel/BKE_curves.hh b/source/blender/blenkernel/BKE_curves.hh
index 82f77d83bec..05a20917552 100644
--- a/source/blender/blenkernel/BKE_curves.hh
+++ b/source/blender/blenkernel/BKE_curves.hh
@@ -77,6 +77,15 @@ class CurvesGeometryRuntime {
mutable std::mutex position_cache_mutex;
mutable bool position_cache_dirty = true;
+ /**
+ * Cache of lengths along each evaluated curve for for each evaluated point. If a curve is
+ * cyclic, it needs one more length value to correspond to the last segment, so in order to
+ * make slicing this array for a curve fast, an extra float is stored for every curve.
+ */
+ mutable Vector<float> evaluated_length_cache;
+ mutable std::mutex length_cache_mutex;
+ mutable bool length_cache_dirty = true;
+
/** Direction of the spline at each evaluated point. */
mutable Vector<float3> evaluated_tangents_cache;
mutable std::mutex tangent_cache_mutex;
@@ -266,6 +275,20 @@ class CurvesGeometry : public ::CurvesGeometry {
Span<float3> evaluated_positions() const;
+ /**
+ * Return a cache of accumulated lengths along the curve. Each item is the length of the
+ * subsequent segment (the first value is the length of the first segment rather than 0).
+ * This calculation is rather trivial, and only depends on the evaluated positions, but
+ * the results are used often, and it is necessarily single threaded per curve, so it is cached.
+ *
+ * \param cyclic: This argument is redundant with the data stored for the curve,
+ * but is passed for performance reasons to avoid looking up the attribute.
+ */
+ Span<float> evaluated_lengths_for_curve(int curve_index, bool cyclic) const;
+
+ /** Calculates the data described by #evaluated_lengths_for_curve if necessary. */
+ void ensure_evaluated_lengths() const;
+
/**
* Evaluate a generic data to the standard evaluated points of a specific curve,
* defined by the resolution attribute or other factors, depending on the curve type.
@@ -281,6 +304,9 @@ class CurvesGeometry : public ::CurvesGeometry {
*/
void ensure_nurbs_basis_cache() const;
+ /** Return the slice of #evaluated_length_cache that corresponds to this curve index. */
+ IndexRange lengths_range_for_curve(int curve_index, bool cyclic) const;
+
/* --------------------------------------------------------------------
* Operations.
*/
diff --git a/source/blender/blenkernel/intern/curves_geometry.cc b/source/blender/blenkernel/intern/curves_geometry.cc
index 7ceaa8f0f37..c4e9a06aad0 100644
--- a/source/blender/blenkernel/intern/curves_geometry.cc
+++ b/source/blender/blenkernel/intern/curves_geometry.cc
@@ -11,6 +11,7 @@
#include "BLI_bounds.hh"
#include "BLI_index_mask_ops.hh"
+#include "BLI_length_parameterize.hh"
#include "DNA_curves_types.h"
@@ -721,6 +722,63 @@ void CurvesGeometry::interpolate_to_evaluated(const int curve_index,
BLI_assert_unreachable();
}
+IndexRange CurvesGeometry::lengths_range_for_curve(const int curve_index, const bool cyclic) const
+{
+ BLI_assert(cyclic == this->cyclic()[curve_index]);
+ const IndexRange points = this->evaluated_points_for_curve(curve_index);
+ const int start = points.start() + curve_index;
+ const int size = curves::curve_segment_size(points.size(), cyclic);
+ return {start, size};
+}
+
+void CurvesGeometry::ensure_evaluated_lengths() const
+{
+ if (!this->runtime->length_cache_dirty) {
+ return;
+ }
+
+ /* A double checked lock. */
+ std::scoped_lock lock{this->runtime->length_cache_mutex};
+ if (!this->runtime->length_cache_dirty) {
+ return;
+ }
+
+ threading::isolate_task([&]() {
+ /* Use an extra length value for the final cyclic segment for a consistent size
+ * (see comment on #evaluated_length_cache). */
+ const int total_size = this->evaluated_points_num() + this->curves_num();
+ this->runtime->evaluated_length_cache.resize(total_size);
+ MutableSpan<float> evaluated_lengths = this->runtime->evaluated_length_cache;
+
+ Span<float3> evaluated_positions = this->evaluated_positions();
+ VArray<bool> curves_cyclic = this->cyclic();
+
+ threading::parallel_for(this->curves_range(), 128, [&](IndexRange curves_range) {
+ for (const int curve_index : curves_range) {
+ const bool cyclic = curves_cyclic[curve_index];
+ const IndexRange evaluated_points = this->evaluated_points_for_curve(curve_index);
+ if (UNLIKELY(evaluated_points.is_empty())) {
+ continue;
+ }
+ const IndexRange lengths_range = this->lengths_range_for_curve(curve_index, cyclic);
+ length_parameterize::accumulate_lengths(evaluated_positions.slice(evaluated_points),
+ cyclic,
+ evaluated_lengths.slice(lengths_range));
+ }
+ });
+ });
+
+ this->runtime->length_cache_dirty = false;
+}
+
+Span<float> CurvesGeometry::evaluated_lengths_for_curve(const int curve_index,
+ const bool cyclic) const
+{
+ BLI_assert(!this->runtime->length_cache_dirty);
+ const IndexRange range = this->lengths_range_for_curve(curve_index, cyclic);
+ return this->runtime->evaluated_length_cache.as_span().slice(range);
+}
+
/** \} */
/* -------------------------------------------------------------------- */
@@ -747,6 +805,7 @@ void CurvesGeometry::tag_positions_changed()
this->runtime->position_cache_dirty = true;
this->runtime->tangent_cache_dirty = true;
this->runtime->normal_cache_dirty = true;
+ this->runtime->length_cache_dirty = true;
}
void CurvesGeometry::tag_topology_changed()
{
@@ -755,6 +814,7 @@ void CurvesGeometry::tag_topology_changed()
this->runtime->normal_cache_dirty = true;
this->runtime->offsets_cache_dirty = true;
this->runtime->nurbs_basis_cache_dirty = true;
+ this->runtime->length_cache_dirty = true;
}
void CurvesGeometry::tag_normals_changed()
{
diff --git a/source/blender/blenlib/BLI_length_parameterize.hh b/source/blender/blenlib/BLI_length_parameterize.hh
new file mode 100644
index 00000000000..e4a4e9cbb9c
--- /dev/null
+++ b/source/blender/blenlib/BLI_length_parameterize.hh
@@ -0,0 +1,80 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#pragma once
+
+/** \file
+ * \ingroup bli
+ */
+
+#include "BLI_math_base.hh"
+#include "BLI_math_color.hh"
+#include "BLI_math_vector.hh"
+#include "BLI_vector.hh"
+
+namespace blender::length_parameterize {
+
+/**
+ * Return the size of the necessary lengths array for a group of points, taking into account the
+ * possible last cyclic segment.
+ *
+ * \note This is the same as #bke::curves::curve_segment_size.
+ */
+inline int lengths_num(const int points_num, const bool cyclic)
+{
+ return cyclic ? points_num : points_num - 1;
+}
+
+/**
+ * Accumulate the length of the next segment into each point.
+ */
+template<typename T>
+void accumulate_lengths(const Span<T> values, const bool cyclic, MutableSpan<float> lengths)
+{
+ BLI_assert(lengths.size() == lengths_num(values.size(), cyclic));
+ float length = 0.0f;
+ for (const int i : IndexRange(values.size() - 1)) {
+ length += math::distance(values[i], values[i + 1]);
+ lengths[i] = length;
+ }
+ if (cyclic) {
+ lengths.last() = length + math::distance(values.last(), values.first());
+ }
+}
+
+template<typename T>
+void linear_interpolation(const Span<T> src,
+ const Span<int> indices,
+ const Span<float> factors,
+ MutableSpan<T> dst)
+{
+ BLI_assert(indices.size() == factors.size());
+ BLI_assert(indices.size() == dst.size());
+ const int last_src_index = src.index_range().last();
+
+ int cyclic_sample_count = 0;
+ for (int i = indices.index_range().last(); i > 0; i--) {
+ if (indices[i] != last_src_index) {
+ break;
+ }
+ dst[i] = math::interpolate(src.last(), src.first(), factors[i]);
+ cyclic_sample_count++;
+ }
+
+ for (const int i : dst.index_range().drop_back(cyclic_sample_count)) {
+ dst[i] = math::interpolate(src[indices[i]], src[indices[i] + 1], factors[i]);
+ }
+}
+
+/**
+ * Find the given number of points, evenly spaced along the provided length. For non-cyclic
+ * sequences, the first point will always be included, and last point will always be included if
+ * the #count is greater than zero. For cyclic sequences, the first point will always be included.
+ *
+ * \warning The #count argument must be greater than zero.
+ */
+void create_uniform_samples(Span<float> lengths,
+ bool cyclic,
+ MutableSpan<int> indices,
+ MutableSpan<float> factors);
+
+} // namespace blender::length_parameterize
diff --git a/source/blender/blenlib/BLI_math_color.hh b/source/blender/blenlib/BLI_math_color.hh
new file mode 100644
index 00000000000..5195cfb6238
--- /dev/null
+++ b/source/blender/blenlib/BLI_math_color.hh
@@ -0,0 +1,28 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later
+ * Copyright 2022 Blender Foundation. */
+
+#pragma once
+
+/** \file
+ * \ingroup bli
+ */
+
+#include <cmath>
+#include <type_traits>
+
+#include "BLI_color.hh"
+#include "BLI_math_base.hh"
+
+namespace blender::math {
+
+inline ColorGeometry4f interpolate(const ColorGeometry4f &a,
+ const ColorGeometry4f &b,
+ const float t)
+{
+ return {math::interpolate(a.r, b.r, t),
+ math::interpolate(a.g, b.g, t),
+ math::interpolate(a.b, b.b, t),
+ math::interpolate(a.a, b.a, t)};
+}
+
+} // namespace blender::math
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index 647726722b1..99e07264276 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -80,6 +80,7 @@ set(SRC
intern/kdtree_4d.c
intern/lasso_2d.c
intern/listbase.c
+ intern/length_parameterize.cc
intern/math_base.c
intern/math_base_inline.c
intern/math_base_safe_inline.c
@@ -225,6 +226,7 @@ set(SRC
BLI_kdtree.h
BLI_kdtree_impl.h
BLI_lasso_2d.h
+ BLI_length_parameterize.hh
BLI_linear_allocator
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list