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
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
|
/*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software Foundation,
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/
#include "BLI_array.hh"
#include "BLI_span.hh"
#include "BLI_timeit.hh"
#include "BKE_spline.hh"
#include "FN_generic_virtual_array.hh"
using blender::Array;
using blender::float3;
using blender::IndexRange;
using blender::MutableSpan;
using blender::Span;
Spline::Type Spline::type() const
{
return type_;
}
void Spline::translate(const blender::float3 &translation)
{
for (float3 &position : this->positions()) {
position += translation;
}
this->mark_cache_invalid();
}
void Spline::transform(const blender::float4x4 &matrix)
{
for (float3 &position : this->positions()) {
position = matrix * position;
}
this->mark_cache_invalid();
}
int Spline::evaluated_edges_size() const
{
const int eval_size = this->evaluated_points_size();
if (eval_size == 1) {
return 0;
}
return this->is_cyclic_ ? eval_size : eval_size - 1;
}
float Spline::length() const
{
Span<float> lengths = this->evaluated_lengths();
return (lengths.size() == 0) ? 0 : this->evaluated_lengths().last();
}
int Spline::segments_size() const
{
const int points_len = this->size();
return is_cyclic_ ? points_len : points_len - 1;
}
bool Spline::is_cyclic() const
{
return is_cyclic_;
}
void Spline::set_cyclic(const bool value)
{
is_cyclic_ = value;
}
static void accumulate_lengths(Span<float3> positions,
const bool is_cyclic,
MutableSpan<float> lengths)
{
float length = 0.0f;
for (const int i : IndexRange(positions.size() - 1)) {
length += float3::distance(positions[i], positions[i + 1]);
lengths[i] = length;
}
if (is_cyclic) {
lengths.last() = length + float3::distance(positions.last(), positions.first());
}
}
/**
* Return non-owning access to the cache of accumulated lengths along the spline. Each item is the
* length of the subsequent segment, i.e. 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.
* However, the results are used often, so it makes sense to cache it.
*/
Span<float> Spline::evaluated_lengths() const
{
if (!length_cache_dirty_) {
return evaluated_lengths_cache_;
}
std::lock_guard lock{length_cache_mutex_};
if (!length_cache_dirty_) {
return evaluated_lengths_cache_;
}
const int total = evaluated_edges_size();
evaluated_lengths_cache_.resize(total);
Span<float3> positions = this->evaluated_positions();
accumulate_lengths(positions, is_cyclic_, evaluated_lengths_cache_);
length_cache_dirty_ = false;
return evaluated_lengths_cache_;
}
static float3 direction_bisect(const float3 &prev, const float3 &middle, const float3 &next)
{
const float3 dir_prev = (middle - prev).normalized();
const float3 dir_next = (next - middle).normalized();
return (dir_prev + dir_next).normalized();
}
static void calculate_tangents(Span<float3> positions,
const bool is_cyclic,
MutableSpan<float3> tangents)
{
if (positions.size() == 1) {
return;
}
for (const int i : IndexRange(1, positions.size() - 2)) {
tangents[i] = direction_bisect(positions[i - 1], positions[i], positions[i + 1]);
}
if (is_cyclic) {
const float3 &second_to_last = positions[positions.size() - 2];
const float3 &last = positions.last();
const float3 &first = positions.first();
const float3 &second = positions[1];
tangents.first() = direction_bisect(last, first, second);
tangents.last() = direction_bisect(second_to_last, last, first);
}
else {
tangents.first() = (positions[1] - positions[0]).normalized();
tangents.last() = (positions.last() - positions[positions.size() - 2]).normalized();
}
}
/**
* Return non-owning access to the direction of the curve at each evaluated point.
*/
Span<float3> Spline::evaluated_tangents() const
{
if (!tangent_cache_dirty_) {
return evaluated_tangents_cache_;
}
std::lock_guard lock{tangent_cache_mutex_};
if (!tangent_cache_dirty_) {
return evaluated_tangents_cache_;
}
const int eval_size = this->evaluated_points_size();
evaluated_tangents_cache_.resize(eval_size);
Span<float3> positions = this->evaluated_positions();
if (eval_size == 1) {
evaluated_tangents_cache_.first() = float3(1.0f, 0.0f, 0.0f);
}
else {
calculate_tangents(positions, is_cyclic_, evaluated_tangents_cache_);
this->correct_end_tangents();
}
tangent_cache_dirty_ = false;
return evaluated_tangents_cache_;
}
static float3 rotate_direction_around_axis(const float3 &direction,
const float3 &axis,
const float angle)
{
BLI_ASSERT_UNIT_V3(direction);
BLI_ASSERT_UNIT_V3(axis);
const float3 axis_scaled = axis * float3::dot(direction, axis);
const float3 diff = direction - axis_scaled;
const float3 cross = float3::cross(axis, diff);
return axis_scaled + diff * std::cos(angle) + cross * std::sin(angle);
}
static void calculate_normals_z_up(Span<float3> tangents, MutableSpan<float3> normals)
{
for (const int i : normals.index_range()) {
normals[i] = float3::cross(tangents[i], float3(0.0f, 0.0f, 1.0f)).normalized();
}
}
/**
* Return non-owning access to the direction vectors perpendicular to the tangents at every
* evaluated point. The method used to generate the normal vectors depends on Spline.normal_mode.
*/
Span<float3> Spline::evaluated_normals() const
{
if (!normal_cache_dirty_) {
return evaluated_normals_cache_;
}
std::lock_guard lock{normal_cache_mutex_};
if (!normal_cache_dirty_) {
return evaluated_normals_cache_;
}
const int eval_size = this->evaluated_points_size();
evaluated_normals_cache_.resize(eval_size);
Span<float3> tangents = evaluated_tangents();
MutableSpan<float3> normals = evaluated_normals_cache_;
/* Only Z up normals are supported at the moment. */
calculate_normals_z_up(tangents, normals);
/* Rotate the generated normals with the interpolated tilt data. */
blender::fn::GVArray_Typed<float> tilts{
this->interpolate_to_evaluated_points(blender::fn::GVArray_For_Span(this->tilts()))};
for (const int i : normals.index_range()) {
normals[i] = rotate_direction_around_axis(normals[i], tangents[i], tilts[i]);
}
normal_cache_dirty_ = false;
return evaluated_normals_cache_;
}
Spline::LookupResult Spline::lookup_evaluated_factor(const float factor) const
{
return this->lookup_evaluated_length(this->length() * factor);
}
/**
* \note This does not support extrapolation currently.
*/
Spline::LookupResult Spline::lookup_evaluated_length(const float length) const
{
BLI_assert(length >= 0.0f && length <= this->length());
Span<float> lengths = this->evaluated_lengths();
const float *offset = std::lower_bound(lengths.begin(), lengths.end(), length);
const int index = offset - lengths.begin();
const int next_index = (index == this->size() - 1) ? 0 : index + 1;
const float previous_length = (index == 0) ? 0.0f : lengths[index - 1];
const float factor = (length - previous_length) / (lengths[index] - previous_length);
return LookupResult{index, next_index, factor};
}
/**
* Return an array of evenly spaced samples along the length of the spline. 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.
*/
Array<float> Spline::sample_uniform_index_factors(const int samples_size) const
{
const Span<float> lengths = this->evaluated_lengths();
BLI_assert(samples_size > 0);
Array<float> samples(samples_size);
samples[0] = 0.0f;
if (samples_size == 1) {
return samples;
}
const float total_length = this->length();
const float sample_length = total_length / (samples_size - 1);
/* 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_sample = 1;
for (const int i_evaluated : IndexRange(this->evaluated_edges_size())) {
const float length = lengths[i_evaluated];
/* Add every sample that fits in this evaluated edge. */
while ((sample_length * i_sample) < length && i_sample < samples_size) {
const float factor = (sample_length * i_sample - prev_length) / (length - prev_length);
samples[i_sample] = i_evaluated + factor;
i_sample++;
}
prev_length = length;
}
samples.last() = lengths.size();
return samples;
}
Spline::LookupResult Spline::lookup_data_from_index_factor(const float index_factor) const
{
const int points_len = this->evaluated_points_size();
if (is_cyclic_) {
if (index_factor < points_len) {
const int index = std::floor(index_factor);
const int next_index = (index < points_len - 1) ? index + 1 : 0;
return LookupResult{index, next_index, index_factor - index};
}
return LookupResult{points_len - 1, 0, 1.0f};
}
if (index_factor < points_len - 1) {
const int index = std::floor(index_factor);
const int next_index = index + 1;
return LookupResult{index, next_index, index_factor - index};
}
return LookupResult{points_len - 2, points_len - 1, 1.0f};
}
void Spline::bounds_min_max(float3 &min, float3 &max, const bool use_evaluated) const
{
Span<float3> positions = use_evaluated ? this->evaluated_positions() : this->positions();
for (const float3 &position : positions) {
minmax_v3v3_v3(min, max, position);
}
}
|