1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
|
/* SPDX-License-Identifier: GPL-2.0-or-later */
#pragma once
/** \file
* \ingroup bli
*/
#include "BLI_index_mask.hh"
#include "BLI_math_base.hh"
#include "BLI_math_color.hh"
#include "BLI_math_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::segments_num.
*/
inline int segments_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() == segments_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>
inline void interpolate_to_masked(const Span<T> src,
const Span<int> indices,
const Span<float> factors,
const IndexMask dst_mask,
MutableSpan<T> dst)
{
BLI_assert(indices.size() == factors.size());
BLI_assert(indices.size() == dst_mask.size());
const int last_src_index = src.size() - 1;
dst_mask.to_best_mask_type([&](auto dst_mask) {
for (const int i : IndexRange(dst_mask.size())) {
const int prev_index = indices[i];
const float factor = factors[i];
const bool is_cyclic_case = prev_index == last_src_index;
if (is_cyclic_case) {
dst[dst_mask[i]] = math::interpolate(src.last(), src.first(), factor);
}
else {
dst[dst_mask[i]] = math::interpolate(src[prev_index], src[prev_index + 1], factor);
}
}
});
}
template<typename T>
inline void interpolate(const Span<T> src,
const Span<int> indices,
const Span<float> factors,
MutableSpan<T> dst)
{
interpolate_to_masked(src, indices, factors, dst.index_range(), dst);
}
/**
* Passing this to consecutive calls of #sample_at_length can increase performance.
*/
struct SampleSegmentHint {
int segment_index = -1;
float segment_start;
float segment_length_inv;
};
/**
* \param accumulated_segment_lengths: Lengths of individual segments added up.
* Each value describes the total length at the end of the segment following a point.
* \param sample_length: The position to sample at.
* \param r_segment_index: Returns the index of the segment that #sample_length is in.
* \param r_factor: Returns the position within the segment.
*
* \note #sample_length must not be outside of any segment.
*/
inline void sample_at_length(const Span<float> accumulated_segment_lengths,
const float sample_length,
int &r_segment_index,
float &r_factor,
SampleSegmentHint *hint = nullptr)
{
/* Use a shorter variable name. */
const Span<float> lengths = accumulated_segment_lengths;
BLI_assert(lengths.size() > 0);
BLI_assert(sample_length >= 0.0f);
BLI_assert(sample_length <= lengths.last());
if (hint != nullptr && hint->segment_index >= 0) {
const float length_in_segment = sample_length - hint->segment_start;
const float factor = length_in_segment * hint->segment_length_inv;
if (factor >= 0.0f && factor < 1.0f) {
r_segment_index = hint->segment_index;
r_factor = factor;
return;
}
}
const float total_length = lengths.last();
if (sample_length >= total_length) {
/* Return the last position on the last segment. */
r_segment_index = lengths.size() - 1;
r_factor = 1.0f;
return;
}
const int prev_point_index = std::upper_bound(lengths.begin(), lengths.end(), sample_length) -
lengths.begin();
const float segment_start = prev_point_index == 0 ? 0.0f : lengths[prev_point_index - 1];
const float segment_end = lengths[prev_point_index];
const float segment_length = segment_end - segment_start;
const float segment_length_inv = math::safe_divide(1.0f, segment_length);
const float length_in_segment = sample_length - segment_start;
const float factor = length_in_segment * segment_length_inv;
r_segment_index = prev_point_index;
r_factor = factor;
if (hint != nullptr) {
hint->segment_index = r_segment_index;
hint->segment_start = segment_start;
hint->segment_length_inv = segment_length_inv;
}
}
/**
* Find evenly spaced samples along the lengths.
*
* \param accumulated_segment_lengths: The accumulated lengths of the original elements being
* sampled. Could be calculated by #accumulate_lengths.
* \param include_last_point: Generally false for cyclic sequences and true otherwise.
* \param r_segment_indices: The index of the previous point at each sample.
* \param r_factors: The portion of the length in each segment at each sample.
*/
void sample_uniform(Span<float> accumulated_segment_lengths,
bool include_last_point,
MutableSpan<int> r_segment_indices,
MutableSpan<float> r_factors);
/**
* For each provided sample length, find the segment index and interpolation factor.
*
* \param accumulated_segment_lengths: The accumulated lengths of the original elements being
* sampled. Could be calculated by #accumulate_lengths.
* \param sample_lengths: Sampled locations in the #lengths array. Must be sorted and is expected
* to be within the range of the #lengths values.
* \param r_segment_indices: The index of the previous point at each sample.
* \param r_factors: The portion of the length in each segment at each sample.
*/
void sample_at_lengths(Span<float> accumulated_segment_lengths,
Span<float> sample_lengths,
MutableSpan<int> r_segment_indices,
MutableSpan<float> r_factors);
} // namespace blender::length_parameterize
|
