From 72d25fa41d8c5753e4cdc1293d407e16c1431119 Mon Sep 17 00:00:00 2001
From: Hans Goudey <h.goudey@me.com>
Date: Tue, 29 Mar 2022 19:44:01 -0500
Subject: 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
---
 .../blender/blenlib/intern/length_parameterize.cc  | 80 ++++++++++++++++++++++
 1 file changed, 80 insertions(+)
 create mode 100644 source/blender/blenlib/intern/length_parameterize.cc

(limited to 'source/blender/blenlib/intern')

diff --git a/source/blender/blenlib/intern/length_parameterize.cc b/source/blender/blenlib/intern/length_parameterize.cc
new file mode 100644
index 00000000000..4947740ba8c
--- /dev/null
+++ b/source/blender/blenlib/intern/length_parameterize.cc
@@ -0,0 +1,80 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#include "BLI_length_parameterize.hh"
+
+namespace blender::length_parameterize {
+
+void create_uniform_samples(const Span<float> lengths,
+                            const bool cyclic,
+                            MutableSpan<int> indices,
+                            MutableSpan<float> factors)
+{
+  const int count = indices.size();
+  BLI_assert(count > 0);
+  BLI_assert(lengths.size() >= 1);
+  BLI_assert(std::is_sorted(lengths.begin(), lengths.end()));
+  const int segments_num = lengths.size();
+  const int points_num = cyclic ? segments_num : segments_num + 1;
+
+  indices.first() = 0;
+  factors.first() = 0.0f;
+  if (count == 1) {
+    return;
+  }
+
+  const float total_length = lengths.last();
+  if (total_length == 0.0f) {
+    indices.fill(0);
+    factors.fill(0.0f);
+    return;
+  }
+
+  const float step_length = total_length / (count - (cyclic ? 0 : 1));
+  const float step_length_inv = 1.0f / step_length;
+
+  int i_dst = 1;
+  /* 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. */
+    const float segment_length_inv = 1.0f / segment_length;
+    const int segment_samples_num = std::ceil(next_length * step_length_inv - i_dst);
+    indices.slice(i_dst, segment_samples_num).fill(i_src);
+
+    for (const int i : factors.index_range().slice(i_dst, segment_samples_num)) {
+      const float length_in_segment = step_length * i - prev_length;
+      factors[i] = length_in_segment * segment_length_inv;
+    }
+
+    i_dst += segment_samples_num;
+
+    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 inacuracy. */
+  if (cyclic && lengths.size() > 1) {
+    indices.drop_front(i_dst).fill(points_num - 1);
+    const float segment_length = lengths.last() - lengths.last(1);
+    if (segment_length == 0.0f) {
+      return;
+    }
+    const float segment_length_inv = 1.0f / segment_length;
+    for (const int i : indices.index_range().drop_front(i_dst)) {
+      const float length_in_segment = step_length * i - prev_length;
+      factors[i] = length_in_segment * segment_length_inv;
+    }
+  }
+  else {
+    indices.drop_front(i_dst).fill(points_num - 2);
+    factors.drop_front(i_dst).fill(1.0f);
+  }
+}
+
+}  // namespace blender::length_parameterize
-- 
cgit v1.2.3