Blender  V3.3
curve_poly.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
7 #include <algorithm>
8 
9 #include "BLI_math_rotation.hh"
10 #include "BLI_math_vector.hh"
11 
12 #include "BKE_curves.hh"
13 
15 
17  const float3 &middle,
18  const float3 &next,
19  bool &r_used_fallback)
20 {
21  const float epsilon = 1e-6f;
22  const bool prev_equal = math::almost_equal_relative(prev, middle, epsilon);
23  const bool next_equal = math::almost_equal_relative(middle, next, epsilon);
24  if (prev_equal && next_equal) {
25  r_used_fallback = true;
26  return {0.0f, 0.0f, 0.0f};
27  }
28  if (prev_equal) {
29  return math::normalize(next - middle);
30  }
31  if (next_equal) {
32  return math::normalize(middle - prev);
33  }
34 
35  const float3 dir_prev = math::normalize(middle - prev);
36  const float3 dir_next = math::normalize(next - middle);
37  const float3 result = math::normalize(dir_prev + dir_next);
38  return result;
39 }
40 
42  const bool is_cyclic,
44 {
45  BLI_assert(positions.size() == tangents.size());
46 
47  if (positions.size() == 1) {
48  tangents.first() = float3(0.0f, 0.0f, 1.0f);
49  return;
50  }
51 
52  bool used_fallback = false;
53 
54  for (const int i : IndexRange(1, positions.size() - 2)) {
56  positions[i - 1], positions[i], positions[i + 1], used_fallback);
57  }
58 
59  if (is_cyclic) {
60  const float3 &second_to_last = positions[positions.size() - 2];
61  const float3 &last = positions.last();
62  const float3 &first = positions.first();
63  const float3 &second = positions[1];
64  tangents.first() = direction_bisect(last, first, second, used_fallback);
65  tangents.last() = direction_bisect(second_to_last, last, first, used_fallback);
66  }
67  else {
68  const float epsilon = 1e-6f;
70  tangents.first() = {0.0f, 0.0f, 0.0f};
71  used_fallback = true;
72  }
73  else {
74  tangents.first() = math::normalize(positions[1] - positions[0]);
75  }
76  if (math::almost_equal_relative(positions.last(0), positions.last(1), epsilon)) {
77  tangents.last() = {0.0f, 0.0f, 0.0f};
78  used_fallback = true;
79  }
80  else {
81  tangents.last() = math::normalize(positions.last(0) - positions.last(1));
82  }
83  }
84 
85  if (!used_fallback) {
86  return;
87  }
88 
89  /* Find the first tangent that does not use the fallback. */
90  int first_valid_tangent_index = -1;
91  for (const int i : tangents.index_range()) {
92  if (!math::is_zero(tangents[i])) {
93  first_valid_tangent_index = i;
94  break;
95  }
96  }
97  if (first_valid_tangent_index == -1) {
98  /* If all tangents used the fallback, it means that all positions are (almost) the same. Just
99  * use the up-vector as default tangent. */
100  const float3 up_vector{0.0f, 0.0f, 1.0f};
101  tangents.fill(up_vector);
102  }
103  else {
104  const float3 &first_valid_tangent = tangents[first_valid_tangent_index];
105  /* If the first few tangents are invalid, use the tangent from the first point with a valid
106  * tangent. */
107  tangents.take_front(first_valid_tangent_index).fill(first_valid_tangent);
108  /* Use the previous valid tangent for points that had no valid tangent. */
109  for (const int i : tangents.index_range().drop_front(first_valid_tangent_index + 1)) {
110  float3 &tangent = tangents[i];
111  if (math::is_zero(tangent)) {
112  const float3 &prev_tangent = tangents[i - 1];
113  tangent = prev_tangent;
114  }
115  }
116  }
117 }
118 
120 {
121  BLI_assert(normals.size() == tangents.size());
122 
123  /* Same as in `vec_to_quat`. */
124  const float epsilon = 1e-4f;
125  for (const int i : normals.index_range()) {
126  const float3 &tangent = tangents[i];
127  if (std::abs(tangent.x) + std::abs(tangent.y) < epsilon) {
128  normals[i] = {1.0f, 0.0f, 0.0f};
129  }
130  else {
131  normals[i] = math::normalize(float3(tangent.y, -tangent.x, 0.0f));
132  }
133  }
134 }
135 
139 static float3 calculate_next_normal(const float3 &last_normal,
140  const float3 &last_tangent,
141  const float3 &current_tangent)
142 {
143  if (math::is_zero(last_tangent) || math::is_zero(current_tangent)) {
144  return last_normal;
145  }
146  const float angle = angle_normalized_v3v3(last_tangent, current_tangent);
147  if (angle != 0.0) {
148  const float3 axis = math::normalize(math::cross(last_tangent, current_tangent));
149  return math::rotate_direction_around_axis(last_normal, axis, angle);
150  }
151  return last_normal;
152 }
153 
155  const bool cyclic,
157 {
158  BLI_assert(normals.size() == tangents.size());
159 
160  if (normals.is_empty()) {
161  return;
162  }
163 
164  const float epsilon = 1e-4f;
165 
166  /* Set initial normal. */
167  const float3 &first_tangent = tangents.first();
168  if (fabs(first_tangent.x) + fabs(first_tangent.y) < epsilon) {
169  normals.first() = {1.0f, 0.0f, 0.0f};
170  }
171  else {
172  normals.first() = math::normalize(float3(first_tangent.y, -first_tangent.x, 0.0f));
173  }
174 
175  /* Forward normal with minimum twist along the entire curve. */
176  for (const int i : IndexRange(1, normals.size() - 1)) {
177  normals[i] = calculate_next_normal(normals[i - 1], tangents[i - 1], tangents[i]);
178  }
179 
180  if (!cyclic) {
181  return;
182  }
183 
184  /* Compute how much the first normal deviates from the normal that has been forwarded along the
185  * entire cyclic curve. */
186  const float3 uncorrected_last_normal = calculate_next_normal(
187  normals.last(), tangents.last(), tangents.first());
188  float correction_angle = angle_signed_on_axis_v3v3_v3(
189  normals.first(), uncorrected_last_normal, tangents.first());
190  if (correction_angle > M_PI) {
191  correction_angle = correction_angle - 2 * M_PI;
192  }
193 
194  /* Gradually apply correction by rotating all normals slightly. */
195  const float angle_step = correction_angle / normals.size();
196  for (const int i : normals.index_range()) {
197  const float angle = angle_step * i;
199  }
200 }
201 
202 } // namespace blender::bke::curves::poly
Low-level operations for curves.
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define M_PI
Definition: BLI_math_base.h:20
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
SIMD_FORCE_INLINE btScalar angle(const btVector3 &v) const
Return the angle between this and another vector.
Definition: btVector3.h:356
static bool is_cyclic(const Nurb *nu)
ccl_device_inline float2 fabs(const float2 &a)
Definition: math_float2.h:222
static ulong * next
void calculate_normals_z_up(Span< float3 > tangents, MutableSpan< float3 > normals)
Definition: curve_poly.cc:119
static float3 direction_bisect(const float3 &prev, const float3 &middle, const float3 &next, bool &r_used_fallback)
Definition: curve_poly.cc:16
void calculate_normals_minimum(Span< float3 > tangents, bool cyclic, MutableSpan< float3 > normals)
Definition: curve_poly.cc:154
static float3 calculate_next_normal(const float3 &last_normal, const float3 &last_tangent, const float3 &current_tangent)
Definition: curve_poly.cc:139
void calculate_tangents(Span< float3 > positions, bool is_cyclic, MutableSpan< float3 > tangents)
Definition: curve_poly.cc:41
vec_base< T, 3 > cross(const vec_base< T, 3 > &a, const vec_base< T, 3 > &b)
bool almost_equal_relative(const vec_base< T, Size > &a, const vec_base< T, Size > &b, const T &epsilon_factor)
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 abs(const T &a)
SymEdge< T > * prev(const SymEdge< T > *se)
Definition: delaunay_2d.cc:105
static double epsilon
vec_base< float, 3 > float3
MutableSpan< float3 > positions
MutableSpan< float3 > tangents
MutableSpan< float3 > normals