Blender  V3.3
spline_base.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
3 #include "BLI_array.hh"
5 #include "BLI_span.hh"
6 #include "BLI_task.hh"
7 #include "BLI_timeit.hh"
8 
9 #include "BKE_attribute_math.hh"
10 #include "BKE_spline.hh"
11 
12 using blender::Array;
13 using blender::float3;
15 using blender::GSpan;
16 using blender::GVArray;
19 using blender::Span;
20 using blender::VArray;
24 
26 {
27  return type_;
28 }
29 
31 {
32  dst.normal_mode = src.normal_mode;
33  dst.is_cyclic_ = src.is_cyclic_;
34 }
35 
37 {
38  switch (type) {
39  case CURVE_TYPE_POLY:
40  return std::make_unique<PolySpline>();
41  case CURVE_TYPE_BEZIER:
42  return std::make_unique<BezierSpline>();
43  case CURVE_TYPE_NURBS:
44  return std::make_unique<NURBSpline>();
47  return {};
48  }
50  return {};
51 }
52 
54 {
55  SplinePtr dst = this->copy_without_attributes();
56  dst->attributes = this->attributes;
57  return dst;
58 }
59 
61 {
63  this->copy_base_settings(*this, *dst);
64  this->copy_settings(*dst);
65  return dst;
66 }
67 
69 {
70  SplinePtr dst = this->copy_only_settings();
71  this->copy_data(*dst);
72 
73  /* Though the attributes storage is empty, it still needs to know the correct size. */
74  dst->attributes.reallocate(dst->size());
75  return dst;
76 }
77 
78 void Spline::translate(const blender::float3 &translation)
79 {
80  for (float3 &position : this->positions()) {
81  position += translation;
82  }
83  this->mark_cache_invalid();
84 }
85 
87 {
88  for (float3 &position : this->positions()) {
89  position = matrix * position;
90  }
91  this->mark_cache_invalid();
92 }
93 
95 {
96  this->positions().reverse();
97  this->radii().reverse();
98  this->tilts().reverse();
99 
101  [&](const AttributeIDRef &id, const AttributeMetaData &meta_data) {
102  std::optional<blender::GMutableSpan> attribute = this->attributes.get_for_write(id);
103  if (!attribute) {
105  return false;
106  }
107  convert_to_static_type(meta_data.data_type, [&](auto dummy) {
108  using T = decltype(dummy);
109  attribute->typed<T>().reverse();
110  });
111  return true;
112  },
114 
115  this->reverse_impl();
116  this->mark_cache_invalid();
117 }
118 
120 {
121  const int eval_num = this->evaluated_points_num();
122  if (eval_num < 2) {
123  /* Two points are required for an edge. */
124  return 0;
125  }
126 
127  return this->is_cyclic_ ? eval_num : eval_num - 1;
128 }
129 
130 float Spline::length() const
131 {
132  Span<float> lengths = this->evaluated_lengths();
133  return lengths.is_empty() ? 0.0f : this->evaluated_lengths().last();
134 }
135 
137 {
138  const int num = this->size();
139 
140  return is_cyclic_ ? num : num - 1;
141 }
142 
143 bool Spline::is_cyclic() const
144 {
145  return is_cyclic_;
146 }
147 
148 void Spline::set_cyclic(const bool value)
149 {
150  is_cyclic_ = value;
151 }
152 
154  const bool is_cyclic,
155  MutableSpan<float> lengths)
156 {
157  using namespace blender::math;
158 
159  float length = 0.0f;
160  for (const int i : IndexRange(positions.size() - 1)) {
161  length += distance(positions[i], positions[i + 1]);
162  lengths[i] = length;
163  }
164  if (is_cyclic) {
165  lengths.last() = length + distance(positions.last(), positions.first());
166  }
167 }
168 
170 {
171  if (!length_cache_dirty_) {
173  }
174 
175  std::lock_guard lock{length_cache_mutex_};
176  if (!length_cache_dirty_) {
178  }
179 
180  const int total = evaluated_edges_num();
182  if (total != 0) {
185  }
186 
187  length_cache_dirty_ = false;
189 }
190 
191 static float3 direction_bisect(const float3 &prev, const float3 &middle, const float3 &next)
192 {
193  using namespace blender::math;
194 
195  const float3 dir_prev = normalize(middle - prev);
196  const float3 dir_next = normalize(next - middle);
197 
198  const float3 result = normalize(dir_prev + dir_next);
199  if (UNLIKELY(is_zero(result))) {
200  return float3(0.0f, 0.0f, 1.0f);
201  }
202  return result;
203 }
204 
206  const bool is_cyclic,
208 {
209  using namespace blender::math;
210 
211  if (positions.size() == 1) {
212  tangents.first() = float3(0.0f, 0.0f, 1.0f);
213  return;
214  }
215 
216  for (const int i : IndexRange(1, positions.size() - 2)) {
217  tangents[i] = direction_bisect(positions[i - 1], positions[i], positions[i + 1]);
218  }
219 
220  if (is_cyclic) {
221  const float3 &second_to_last = positions[positions.size() - 2];
222  const float3 &last = positions.last();
223  const float3 &first = positions.first();
224  const float3 &second = positions[1];
225  tangents.first() = direction_bisect(last, first, second);
226  tangents.last() = direction_bisect(second_to_last, last, first);
227  }
228  else {
229  tangents.first() = normalize(positions[1] - positions[0]);
230  tangents.last() = normalize(positions.last() - positions[positions.size() - 2]);
231  }
232 }
233 
235 {
236  if (!tangent_cache_dirty_) {
238  }
239 
240  std::lock_guard lock{tangent_cache_mutex_};
241  if (!tangent_cache_dirty_) {
243  }
244 
245  const int eval_num = this->evaluated_points_num();
246  evaluated_tangents_cache_.resize(eval_num);
247 
249 
251  this->correct_end_tangents();
252 
253  tangent_cache_dirty_ = false;
255 }
256 
258  const float3 &axis,
259  const float angle)
260 {
261  using namespace blender::math;
262 
263  BLI_ASSERT_UNIT_V3(direction);
264  BLI_ASSERT_UNIT_V3(axis);
265 
266  const float3 axis_scaled = axis * dot(direction, axis);
267  const float3 diff = direction - axis_scaled;
268  const float3 cross = blender::math::cross(axis, diff);
269 
270  return axis_scaled + diff * std::cos(angle) + cross * std::sin(angle);
271 }
272 
274 {
275  using namespace blender::math;
276 
277  BLI_assert(r_normals.size() == tangents.size());
278 
279  /* Same as in `vec_to_quat`. */
280  const float epsilon = 1e-4f;
281  for (const int i : r_normals.index_range()) {
282  const float3 &tangent = tangents[i];
283  if (fabsf(tangent.x) + fabsf(tangent.y) < epsilon) {
284  r_normals[i] = {1.0f, 0.0f, 0.0f};
285  }
286  else {
287  r_normals[i] = normalize(float3(tangent.y, -tangent.x, 0.0f));
288  }
289  }
290 }
291 
295 static float3 calculate_next_normal(const float3 &last_normal,
296  const float3 &last_tangent,
297  const float3 &current_tangent)
298 {
299  using namespace blender::math;
300 
301  if (is_zero(last_tangent) || is_zero(current_tangent)) {
302  return last_normal;
303  }
304  const float angle = angle_normalized_v3v3(last_tangent, current_tangent);
305  if (angle != 0.0) {
306  const float3 axis = normalize(cross(last_tangent, current_tangent));
307  return rotate_direction_around_axis(last_normal, axis, angle);
308  }
309  return last_normal;
310 }
311 
313  const bool cyclic,
314  MutableSpan<float3> r_normals)
315 {
316  using namespace blender::math;
317  BLI_assert(r_normals.size() == tangents.size());
318 
319  if (r_normals.is_empty()) {
320  return;
321  }
322 
323  const float epsilon = 1e-4f;
324 
325  /* Set initial normal. */
326  const float3 &first_tangent = tangents[0];
327  if (fabs(first_tangent.x) + fabs(first_tangent.y) < epsilon) {
328  r_normals[0] = {1.0f, 0.0f, 0.0f};
329  }
330  else {
331  r_normals[0] = normalize(float3(first_tangent.y, -first_tangent.x, 0.0f));
332  }
333 
334  /* Forward normal with minimum twist along the entire spline. */
335  for (const int i : IndexRange(1, r_normals.size() - 1)) {
336  r_normals[i] = calculate_next_normal(r_normals[i - 1], tangents[i - 1], tangents[i]);
337  }
338 
339  if (!cyclic) {
340  return;
341  }
342 
343  /* Compute how much the first normal deviates from the normal that has been forwarded along the
344  * entire cyclic spline. */
345  const float3 uncorrected_last_normal = calculate_next_normal(
346  r_normals.last(), tangents.last(), tangents[0]);
347  float correction_angle = angle_signed_on_axis_v3v3_v3(
348  r_normals[0], uncorrected_last_normal, tangents[0]);
349  if (correction_angle > M_PI) {
350  correction_angle = correction_angle - 2 * M_PI;
351  }
352 
353  /* Gradually apply correction by rotating all normals slightly. */
354  const float angle_step = correction_angle / r_normals.size();
355  for (const int i : r_normals.index_range()) {
356  const float angle = angle_step * i;
357  r_normals[i] = rotate_direction_around_axis(r_normals[i], tangents[i], angle);
358  }
359 }
360 
362 {
363  if (!normal_cache_dirty_) {
365  }
366 
367  std::lock_guard lock{normal_cache_mutex_};
368  if (!normal_cache_dirty_) {
370  }
371 
372  const int eval_num = this->evaluated_points_num();
373  evaluated_normals_cache_.resize(eval_num);
374 
377 
378  /* Only Z up normals are supported at the moment. */
379  switch (this->normal_mode) {
380  case NORMAL_MODE_Z_UP: {
381  calculate_normals_z_up(tangents, normals);
382  break;
383  }
386  break;
387  }
388  }
389 
390  /* Rotate the generated normals with the interpolated tilt data. */
392  for (const int i : normals.index_range()) {
394  }
395 
396  normal_cache_dirty_ = false;
398 }
399 
401 {
402  return this->lookup_evaluated_length(this->length() * factor);
403 }
404 
406 {
407  BLI_assert(length >= 0.0f && length <= this->length());
408 
409  Span<float> lengths = this->evaluated_lengths();
410 
411  const float *offset = std::lower_bound(lengths.begin(), lengths.end(), length);
412  const int index = offset - lengths.begin();
413  const int next_index = (index == this->evaluated_points_num() - 1) ? 0 : index + 1;
414 
415  const float previous_length = (index == 0) ? 0.0f : lengths[index - 1];
416  const float length_in_segment = length - previous_length;
417  const float segment_length = lengths[index] - previous_length;
418  const float factor = segment_length == 0.0f ? 0.0f : length_in_segment / segment_length;
419 
420  return LookupResult{index, next_index, factor};
421 }
422 
424 {
425  const Span<float> lengths = this->evaluated_lengths();
426 
427  BLI_assert(samples_num > 0);
428  Array<float> samples(samples_num);
429 
430  samples[0] = 0.0f;
431  if (samples_num == 1) {
432  return samples;
433  }
434 
435  const float total_length = this->length();
436  const float sample_length = total_length / (samples_num - (is_cyclic_ ? 0 : 1));
437 
438  /* Store the length at the previous evaluated point in a variable so it can
439  * start out at zero (the lengths array doesn't contain 0 for the first point). */
440  float prev_length = 0.0f;
441  int i_sample = 1;
442  for (const int i_evaluated : IndexRange(this->evaluated_edges_num())) {
443  const float length = lengths[i_evaluated];
444 
445  /* Add every sample that fits in this evaluated edge. */
446  while ((sample_length * i_sample) < length && i_sample < samples_num) {
447  const float factor = (sample_length * i_sample - prev_length) / (length - prev_length);
448  samples[i_sample] = i_evaluated + factor;
449  i_sample++;
450  }
451 
452  prev_length = length;
453  }
454 
455  /* Zero lengths or float inaccuracies can cause invalid values, or simply
456  * skip some, so set the values that weren't completed in the main loop. */
457  for (const int i : IndexRange(i_sample, samples_num - i_sample)) {
458  samples[i] = float(samples_num);
459  }
460 
461  if (!is_cyclic_) {
462  /* In rare cases this can prevent overflow of the stored index. */
463  samples.last() = lengths.size();
464  }
465 
466  return samples;
467 }
468 
470 {
471  const int eval_num = this->evaluated_points_num();
472 
473  if (is_cyclic_) {
474  if (index_factor < eval_num) {
475  const int index = std::floor(index_factor);
476  const int next_index = (index < eval_num - 1) ? index + 1 : 0;
477  return LookupResult{index, next_index, index_factor - index};
478  }
479  return LookupResult{eval_num - 1, 0, 1.0f};
480  }
481 
482  if (index_factor < eval_num - 1) {
483  const int index = std::floor(index_factor);
484  const int next_index = index + 1;
485  return LookupResult{index, next_index, index_factor - index};
486  }
487  return LookupResult{eval_num - 2, eval_num - 1, 1.0f};
488 }
489 
490 void Spline::bounds_min_max(float3 &min, float3 &max, const bool use_evaluated) const
491 {
492  Span<float3> positions = use_evaluated ? this->evaluated_positions() : this->positions();
493  for (const float3 &position : positions) {
494  minmax_v3v3_v3(min, max, position);
495  }
496 }
497 
499 {
500  return this->interpolate_to_evaluated(GVArray::ForSpan(data));
501 }
502 
504  Span<float> index_factors,
505  GMutableSpan dst) const
506 {
507  BLI_assert(src.size() == this->evaluated_points_num());
508 
509  blender::attribute_math::convert_to_static_type(src.type(), [&](auto dummy) {
510  using T = decltype(dummy);
511  const VArray<T> src_typed = src.typed<T>();
512  MutableSpan<T> dst_typed = dst.typed<T>();
513  if (src.size() == 1) {
514  dst_typed.fill(src_typed[0]);
515  return;
516  }
517  blender::threading::parallel_for(dst_typed.index_range(), 1024, [&](IndexRange range) {
518  for (const int i : range) {
519  const LookupResult interp = this->lookup_data_from_index_factor(index_factors[i]);
520  dst_typed[i] = blender::attribute_math::mix2(interp.factor,
521  src_typed[interp.evaluated_index],
522  src_typed[interp.next_evaluated_index]);
523  }
524  });
525  });
526 }
typedef float(TangentPoint)[2]
@ ATTR_DOMAIN_POINT
Definition: BKE_attribute.h:27
std::unique_ptr< Spline > SplinePtr
Definition: BKE_spline.hh:26
#define BLI_assert_unreachable()
Definition: BLI_assert.h:93
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define BLI_ASSERT_UNIT_V3(v)
#define M_PI
Definition: BLI_math_base.h:20
void minmax_v3v3_v3(float min[3], float max[3], const float vec[3])
Definition: math_vector.c:867
float angle_signed_on_axis_v3v3_v3(const float v1[3], const float v2[3], const float axis[3]) ATTR_WARN_UNUSED_RESULT
Definition: math_vector.c:488
float angle_normalized_v3v3(const float v1[3], const float v2[3]) ATTR_WARN_UNUSED_RESULT
Definition: math_vector.c:445
#define UNLIKELY(x)
CurveType
@ CURVE_TYPE_BEZIER
@ CURVE_TYPE_NURBS
@ CURVE_TYPE_POLY
@ CURVE_TYPE_CATMULL_ROM
@ NORMAL_MODE_MINIMUM_TWIST
@ NORMAL_MODE_Z_UP
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum type
in reality light always falls off quadratically Particle Retrieve the data of the particle that spawned the object for example to give variation to multiple instances of an object Point Retrieve information about points in a point cloud Retrieve the edges of an object as it appears to Cycles topology will always appear triangulated Convert a blackbody temperature to an RGB value Normal Generate a perturbed normal from an RGB normal map image Typically used for faking highly detailed surfaces Generate an OSL shader from a file or text data block Image Sample an image file as a texture Sky Generate a procedural sky texture Noise Generate fractal Perlin noise Wave Generate procedural bands or rings with noise Voronoi Generate Worley noise based on the distance to random points Typically used to generate textures such as or biological cells Brick Generate a procedural texture producing bricks Texture Retrieve multiple types of texture coordinates nTypically used as inputs for texture nodes Vector Convert a or normal between and object coordinate space Combine Create a color from its and value channels Color Retrieve a color attribute
volatile int lock
SIMD_FORCE_INLINE btScalar angle(const btVector3 &v) const
Return the angle between this and another vector.
Definition: btVector3.h:356
LookupResult lookup_evaluated_factor(float factor) const
Definition: spline_base.cc:400
std::mutex tangent_cache_mutex_
Definition: BKE_spline.hh:64
virtual void translate(const blender::float3 &translation)
Definition: spline_base.cc:78
virtual blender::MutableSpan< blender::float3 > positions()=0
CurveType type() const
Definition: spline_base.cc:25
std::mutex length_cache_mutex_
Definition: BKE_spline.hh:74
virtual blender::MutableSpan< float > tilts()=0
int evaluated_edges_num() const
Definition: spline_base.cc:119
blender::Span< float > evaluated_lengths() const
Definition: spline_base.cc:169
SplinePtr copy_without_attributes() const
Definition: spline_base.cc:68
CurveType type_
Definition: BKE_spline.hh:59
bool tangent_cache_dirty_
Definition: BKE_spline.hh:65
blender::Array< float > sample_uniform_index_factors(int samples_num) const
Definition: spline_base.cc:423
void set_cyclic(bool value)
Definition: spline_base.cc:148
virtual void transform(const blender::float4x4 &matrix)
Definition: spline_base.cc:86
void bounds_min_max(blender::float3 &min, blender::float3 &max, bool use_evaluated) const
Definition: spline_base.cc:490
blender::Vector< blender::float3 > evaluated_tangents_cache_
Definition: BKE_spline.hh:63
SplinePtr copy() const
Definition: spline_base.cc:53
std::mutex normal_cache_mutex_
Definition: BKE_spline.hh:69
blender::Vector< float > evaluated_lengths_cache_
Definition: BKE_spline.hh:73
virtual int size() const =0
bool is_cyclic_
Definition: BKE_spline.hh:60
NormalMode normal_mode
Definition: BKE_spline.hh:54
float length() const
Definition: spline_base.cc:130
virtual int evaluated_points_num() const =0
LookupResult lookup_data_from_index_factor(float index_factor) const
Definition: spline_base.cc:469
virtual void reverse_impl()=0
blender::Vector< blender::float3 > evaluated_normals_cache_
Definition: BKE_spline.hh:68
blender::Span< blender::float3 > evaluated_normals() const
Definition: spline_base.cc:361
blender::bke::CustomDataAttributes attributes
Definition: BKE_spline.hh:56
void sample_with_index_factors(const blender::GVArray &src, blender::Span< float > index_factors, blender::GMutableSpan dst) const
Definition: spline_base.cc:503
static void copy_base_settings(const Spline &src, Spline &dst)
Definition: spline_base.cc:30
virtual blender::MutableSpan< float > radii()=0
virtual void mark_cache_invalid()=0
void reverse()
Definition: spline_base.cc:94
bool is_cyclic() const
Definition: spline_base.cc:143
virtual blender::GVArray interpolate_to_evaluated(const blender::GVArray &src) const =0
bool normal_cache_dirty_
Definition: BKE_spline.hh:70
virtual void copy_settings(Spline &dst) const =0
virtual blender::Span< blender::float3 > evaluated_positions() const =0
LookupResult lookup_evaluated_length(float length) const
Definition: spline_base.cc:405
blender::Span< blender::float3 > evaluated_tangents() const
Definition: spline_base.cc:234
bool length_cache_dirty_
Definition: BKE_spline.hh:75
int segments_num() const
Definition: spline_base.cc:136
SplinePtr copy_only_settings() const
Definition: spline_base.cc:60
virtual void correct_end_tangents() const =0
virtual void copy_data(Spline &dst) const =0
const T & last(const int64_t n=0) const
Definition: BLI_array.hh:284
constexpr int64_t size() const
Definition: BLI_span.hh:511
constexpr bool is_empty() const
Definition: BLI_span.hh:519
constexpr T & last(const int64_t n=0) const
Definition: BLI_span.hh:680
constexpr IndexRange index_range() const
Definition: BLI_span.hh:661
constexpr const T & last(const int64_t n=0) const
Definition: BLI_span.hh:313
constexpr int64_t size() const
Definition: BLI_span.hh:240
constexpr const T * end() const
Definition: BLI_span.hh:212
constexpr const T * begin() const
Definition: BLI_span.hh:208
constexpr bool is_empty() const
Definition: BLI_span.hh:248
void resize(const int64_t new_size)
Definition: BLI_vector.hh:353
std::optional< blender::GMutableSpan > get_for_write(const AttributeIDRef &attribute_id)
bool foreach_attribute(const AttributeForeachCallback callback, eAttrDomain domain) const
SyclQueue void void * src
static bool is_cyclic(const Nurb *nu)
ccl_gpu_kernel_postfix ccl_global float int int int int float bool int offset
ccl_device_inline float2 fabs(const float2 &a)
Definition: math_float2.h:222
static ulong * next
#define fabsf(x)
Definition: metal/compat.h:219
IMETHOD Vector diff(const Vector &a, const Vector &b, double dt=1)
INLINE Rall1d< T, V, S > cos(const Rall1d< T, V, S > &arg)
Definition: rall1d.h:319
INLINE Rall1d< T, V, S > sin(const Rall1d< T, V, S > &arg)
Definition: rall1d.h:311
void convert_to_static_type(const CPPType &cpp_type, const Func &func)
T dot(const vec_base< T, Size > &a, const vec_base< T, Size > &b)
vec_base< T, 3 > cross(const vec_base< T, 3 > &a, const vec_base< T, 3 > &b)
T length(const vec_base< T, Size > &a)
T distance(const T &a, const T &b)
vec_base< T, Size > normalize(const vec_base< T, Size > &v)
bool is_zero(const T &a)
float3 rotate_direction_around_axis(const float3 &direction, const float3 &axis, float angle)
T floor(const T &a)
SymEdge< T > * prev(const SymEdge< T > *se)
Definition: delaunay_2d.cc:105
static double epsilon
void parallel_for(IndexRange range, int64_t grain_size, const Function &function)
Definition: BLI_task.hh:51
vec_base< float, 3 > float3
MutableSpan< float3 > positions
MutableSpan< float3 > tangents
MutableSpan< float3 > normals
#define min(a, b)
Definition: sort.c:35
static float3 calculate_next_normal(const float3 &last_normal, const float3 &last_tangent, const float3 &current_tangent)
Definition: spline_base.cc:295
static void calculate_normals_z_up(Span< float3 > tangents, MutableSpan< float3 > r_normals)
Definition: spline_base.cc:273
static SplinePtr create_spline(const CurveType type)
Definition: spline_base.cc:36
static void calculate_normals_minimum(Span< float3 > tangents, const bool cyclic, MutableSpan< float3 > r_normals)
Definition: spline_base.cc:312
static float3 rotate_direction_around_axis(const float3 &direction, const float3 &axis, const float angle)
Definition: spline_base.cc:257
static float3 direction_bisect(const float3 &prev, const float3 &middle, const float3 &next)
Definition: spline_base.cc:191
static void accumulate_lengths(Span< float3 > positions, const bool is_cyclic, MutableSpan< float > lengths)
Definition: spline_base.cc:153
static void calculate_tangents(Span< float3 > positions, const bool is_cyclic, MutableSpan< float3 > tangents)
Definition: spline_base.cc:205
float y
float x
float max