Blender  V3.3
add_curves_on_mesh.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
4 
5 #include "BKE_attribute_math.hh"
6 #include "BKE_mesh_sample.hh"
7 
10 
17 namespace blender::geometry {
18 
20 
21 struct NeighborCurve {
22  /* Curve index of the neighbor. */
23  int index;
24  /* The weights of all neighbors of a new curve add up to 1. */
25  float weight;
26 };
27 
28 static constexpr int max_neighbors = 5;
30 
32  const float3 &bary_coord,
33  const Span<float3> corner_normals)
34 {
35  const int l0 = looptri.tri[0];
36  const int l1 = looptri.tri[1];
37  const int l2 = looptri.tri[2];
38 
39  const float3 &l0_normal = corner_normals[l0];
40  const float3 &l1_normal = corner_normals[l1];
41  const float3 &l2_normal = corner_normals[l2];
42 
44  attribute_math::mix3(bary_coord, l0_normal, l1_normal, l2_normal));
45  return normal;
46 }
47 
49  const float3 &p2,
50  MutableSpan<float3> r_positions)
51 {
52  const float step = 1.0f / (float)(r_positions.size() - 1);
53  for (const int i : r_positions.index_range()) {
54  r_positions[i] = math::interpolate(p1, p2, i * step);
55  }
56 }
57 
59  const KDTree_3d &old_roots_kdtree)
60 {
61  const int tot_added_curves = root_positions.size();
62  Array<NeighborCurves> neighbors_per_curve(tot_added_curves);
63  threading::parallel_for(IndexRange(tot_added_curves), 128, [&](const IndexRange range) {
64  for (const int i : range) {
65  const float3 root = root_positions[i];
66  std::array<KDTreeNearest_3d, max_neighbors> nearest_n;
67  const int found_neighbors = BLI_kdtree_3d_find_nearest_n(
68  &old_roots_kdtree, root, nearest_n.data(), max_neighbors);
69  float tot_weight = 0.0f;
70  for (const int neighbor_i : IndexRange(found_neighbors)) {
71  KDTreeNearest_3d &nearest = nearest_n[neighbor_i];
72  const float weight = 1.0f / std::max(nearest.dist, 0.00001f);
73  tot_weight += weight;
74  neighbors_per_curve[i].append({nearest.index, weight});
75  }
76  /* Normalize weights. */
77  for (NeighborCurve &neighbor : neighbors_per_curve[i]) {
78  neighbor.weight /= tot_weight;
79  }
80  }
81  });
82  return neighbors_per_curve;
83 }
84 
85 template<typename T, typename GetValueF>
86 void interpolate_from_neighbors(const Span<NeighborCurves> neighbors_per_curve,
87  const T &fallback,
88  const GetValueF &get_value_from_neighbor,
89  MutableSpan<T> r_interpolated_values)
90 {
91  attribute_math::DefaultMixer<T> mixer{r_interpolated_values};
92  threading::parallel_for(r_interpolated_values.index_range(), 512, [&](const IndexRange range) {
93  for (const int i : range) {
94  const NeighborCurves &neighbors = neighbors_per_curve[i];
95  if (neighbors.is_empty()) {
96  mixer.mix_in(i, fallback, 1.0f);
97  }
98  else {
99  for (const NeighborCurve &neighbor : neighbors) {
100  const T neighbor_value = get_value_from_neighbor(neighbor.index);
101  mixer.mix_in(i, neighbor_value, neighbor.weight);
102  }
103  }
104  }
105  });
106  mixer.finalize();
107 }
108 
111  const int old_curves_num,
112  const Span<float3> root_positions_cu,
113  const Span<float> new_lengths_cu,
114  const Span<float3> new_normals_su,
115  const float4x4 &surface_to_curves_normal_mat)
116 {
117  const int added_curves_num = root_positions_cu.size();
118  MutableSpan<float3> positions_cu = curves.positions_for_write();
119  threading::parallel_for(IndexRange(added_curves_num), 256, [&](const IndexRange range) {
120  for (const int i : range) {
121  const int curve_i = old_curves_num + i;
122  const IndexRange points = curves.points_for_curve(curve_i);
123  const float3 &root_cu = root_positions_cu[i];
124  const float length = new_lengths_cu[i];
125  const float3 &normal_su = new_normals_su[i];
126  const float3 normal_cu = math::normalize(surface_to_curves_normal_mat * normal_su);
127  const float3 tip_cu = root_cu + length * normal_cu;
128 
129  initialize_straight_curve_positions(root_cu, tip_cu, positions_cu.slice(points));
130  }
131  });
132 }
133 
135  const Span<float3> root_positions_cu,
136  const Span<NeighborCurves> neighbors_per_curve,
137  const int old_curves_num,
138  const Span<float> new_lengths_cu,
139  const Span<float3> new_normals_su,
140  const bke::CurvesSurfaceTransforms &transforms,
141  const ReverseUVSampler &reverse_uv_sampler,
142  const Span<float3> corner_normals_su)
143 {
144  MutableSpan<float3> positions_cu = curves.positions_for_write();
145  const int added_curves_num = root_positions_cu.size();
146 
147  const Span<float2> uv_coords = curves.surface_uv_coords();
148 
149  threading::parallel_for(IndexRange(added_curves_num), 256, [&](const IndexRange range) {
150  for (const int added_curve_i : range) {
151  const NeighborCurves &neighbors = neighbors_per_curve[added_curve_i];
152  const int curve_i = old_curves_num + added_curve_i;
153  const IndexRange points = curves.points_for_curve(curve_i);
154 
155  const float length_cu = new_lengths_cu[added_curve_i];
156  const float3 &normal_su = new_normals_su[added_curve_i];
157  const float3 normal_cu = math::normalize(transforms.surface_to_curves_normal * normal_su);
158 
159  const float3 &root_cu = root_positions_cu[added_curve_i];
160 
161  if (neighbors.is_empty()) {
162  /* If there are no neighbors, just make a straight line. */
163  const float3 tip_cu = root_cu + length_cu * normal_cu;
164  initialize_straight_curve_positions(root_cu, tip_cu, positions_cu.slice(points));
165  continue;
166  }
167 
168  positions_cu.slice(points).fill(root_cu);
169 
170  for (const NeighborCurve &neighbor : neighbors) {
171  const int neighbor_curve_i = neighbor.index;
172  const float2 neighbor_uv = uv_coords[neighbor_curve_i];
173  const ReverseUVSampler::Result result = reverse_uv_sampler.sample(neighbor_uv);
174  if (result.type != ReverseUVSampler::ResultType::Ok) {
175  continue;
176  }
177 
178  const float3 neighbor_normal_su = compute_surface_point_normal(
179  *result.looptri, result.bary_weights, corner_normals_su);
180  const float3 neighbor_normal_cu = math::normalize(transforms.surface_to_curves_normal *
181  neighbor_normal_su);
182 
183  /* The rotation matrix used to transform relative coordinates of the neighbor curve
184  * to the new curve. */
185  float normal_rotation_cu[3][3];
186  rotation_between_vecs_to_mat3(normal_rotation_cu, neighbor_normal_cu, normal_cu);
187 
188  const IndexRange neighbor_points = curves.points_for_curve(neighbor_curve_i);
189  const float3 &neighbor_root_cu = positions_cu[neighbor_points[0]];
190 
191  /* Sample the positions on neighbors and mix them into the final positions of the curve.
192  * Resampling is necessary if the length of the new curve does not match the length of the
193  * neighbors or the number of handle points is different.
194  *
195  * TODO: The lengths can be cached so they aren't recomputed if a curve is a neighbor for
196  * multiple new curves. Also, allocations could be avoided by reusing some arrays. */
197 
198  const Span<float3> neighbor_positions_cu = positions_cu.slice(neighbor_points);
199  if (neighbor_positions_cu.size() == 1) {
200  /* Skip interpolating positions from neighbors with only one point. */
201  continue;
202  }
203  Array<float, 32> lengths(length_parameterize::segments_num(neighbor_points.size(), false));
204  length_parameterize::accumulate_lengths<float3>(neighbor_positions_cu, false, lengths);
205  const float neighbor_length_cu = lengths.last();
206 
207  Array<float, 32> sample_lengths(points.size());
208  const float length_factor = std::min(1.0f, length_cu / neighbor_length_cu);
209  const float resample_factor = (1.0f / (points.size() - 1.0f)) * length_factor;
210  for (const int i : sample_lengths.index_range()) {
211  sample_lengths[i] = i * resample_factor * neighbor_length_cu;
212  }
213 
214  Array<int, 32> indices(points.size());
215  Array<float, 32> factors(points.size());
216  length_parameterize::sample_at_lengths(lengths, sample_lengths, indices, factors);
217 
218  for (const int i : IndexRange(points.size())) {
219  const float3 sample_cu = math::interpolate(neighbor_positions_cu[indices[i]],
220  neighbor_positions_cu[indices[i] + 1],
221  factors[i]);
222  const float3 relative_to_root_cu = sample_cu - neighbor_root_cu;
223  float3 rotated_relative_coord = relative_to_root_cu;
224  mul_m3_v3(normal_rotation_cu, rotated_relative_coord);
225  positions_cu[points[i]] += neighbor.weight * rotated_relative_coord;
226  }
227  }
228  }
229  });
230 }
231 
234 {
236 
237  const bool use_interpolation = inputs.interpolate_length || inputs.interpolate_point_count ||
238  inputs.interpolate_shape;
239 
240  Vector<float3> root_positions_cu;
241  Vector<float3> bary_coords;
242  Vector<const MLoopTri *> looptris;
243  Vector<float2> used_uvs;
244 
245  /* Find faces that the passed in uvs belong to. */
246  for (const int i : inputs.uvs.index_range()) {
247  const float2 &uv = inputs.uvs[i];
248  const ReverseUVSampler::Result result = inputs.reverse_uv_sampler->sample(uv);
249  if (result.type != ReverseUVSampler::ResultType::Ok) {
250  outputs.uv_error = true;
251  continue;
252  }
253  const MLoopTri &looptri = *result.looptri;
254  bary_coords.append(result.bary_weights);
255  looptris.append(&looptri);
256  const float3 root_position_su = attribute_math::mix3<float3>(
257  result.bary_weights,
258  inputs.surface->mvert[inputs.surface->mloop[looptri.tri[0]].v].co,
259  inputs.surface->mvert[inputs.surface->mloop[looptri.tri[1]].v].co,
260  inputs.surface->mvert[inputs.surface->mloop[looptri.tri[2]].v].co);
261  root_positions_cu.append(inputs.transforms->surface_to_curves * root_position_su);
262  used_uvs.append(uv);
263  }
264 
265  Array<NeighborCurves> neighbors_per_curve;
266  if (use_interpolation) {
267  BLI_assert(inputs.old_roots_kdtree != nullptr);
268  neighbors_per_curve = find_curve_neighbors(root_positions_cu, *inputs.old_roots_kdtree);
269  }
270 
271  const int added_curves_num = root_positions_cu.size();
272  const int old_points_num = curves.points_num();
273  const int old_curves_num = curves.curves_num();
274  const int new_curves_num = old_curves_num + added_curves_num;
275 
276  /* Grow number of curves first, so that the offsets array can be filled. */
277  curves.resize(old_points_num, new_curves_num);
278 
279  /* Compute new curve offsets. */
280  MutableSpan<int> curve_offsets = curves.offsets_for_write();
281  MutableSpan<int> new_point_counts_per_curve = curve_offsets.take_back(added_curves_num);
282  if (inputs.interpolate_point_count) {
283  interpolate_from_neighbors<int>(
284  neighbors_per_curve,
285  inputs.fallback_point_count,
286  [&](const int curve_i) { return curves.points_for_curve(curve_i).size(); },
287  new_point_counts_per_curve);
288  }
289  else {
290  new_point_counts_per_curve.fill(inputs.fallback_point_count);
291  }
292  for (const int i : IndexRange(added_curves_num)) {
293  curve_offsets[old_curves_num + i + 1] += curve_offsets[old_curves_num + i];
294  }
295 
296  const int new_points_num = curves.offsets().last();
297  curves.resize(new_points_num, new_curves_num);
298  MutableSpan<float3> positions_cu = curves.positions_for_write();
299 
300  /* Initialize attachment information. */
301  MutableSpan<float2> surface_uv_coords = curves.surface_uv_coords_for_write();
302  surface_uv_coords.take_back(added_curves_num).copy_from(used_uvs);
303 
304  /* Determine length of new curves. */
305  Array<float> new_lengths_cu(added_curves_num);
306  if (inputs.interpolate_length) {
307  interpolate_from_neighbors<float>(
308  neighbors_per_curve,
309  inputs.fallback_curve_length,
310  [&](const int curve_i) {
311  const IndexRange points = curves.points_for_curve(curve_i);
312  float length = 0.0f;
313  for (const int segment_i : points.drop_back(1)) {
314  const float3 &p1 = positions_cu[segment_i];
315  const float3 &p2 = positions_cu[segment_i + 1];
316  length += math::distance(p1, p2);
317  }
318  return length;
319  },
320  new_lengths_cu);
321  }
322  else {
323  new_lengths_cu.fill(inputs.fallback_curve_length);
324  }
325 
326  /* Find surface normal at root points. */
327  Array<float3> new_normals_su(added_curves_num);
328  threading::parallel_for(IndexRange(added_curves_num), 256, [&](const IndexRange range) {
329  for (const int i : range) {
330  new_normals_su[i] = compute_surface_point_normal(
331  *looptris[i], bary_coords[i], inputs.corner_normals_su);
332  }
333  });
334 
335  /* Update selection arrays when available. */
336  const VArray<float> points_selection = curves.selection_point_float();
337  if (points_selection.is_span()) {
338  MutableSpan<float> points_selection_span = curves.selection_point_float_for_write();
339  points_selection_span.drop_front(old_points_num).fill(1.0f);
340  }
341  const VArray<float> curves_selection = curves.selection_curve_float();
342  if (curves_selection.is_span()) {
343  MutableSpan<float> curves_selection_span = curves.selection_curve_float_for_write();
344  curves_selection_span.drop_front(old_curves_num).fill(1.0f);
345  }
346 
347  /* Initialize position attribute. */
348  if (inputs.interpolate_shape) {
350  root_positions_cu,
351  neighbors_per_curve,
352  old_curves_num,
353  new_lengths_cu,
354  new_normals_su,
355  *inputs.transforms,
356  *inputs.reverse_uv_sampler,
357  inputs.corner_normals_su);
358  }
359  else {
361  old_curves_num,
362  root_positions_cu,
363  new_lengths_cu,
364  new_normals_su,
365  inputs.transforms->surface_to_curves_normal);
366  }
367 
368  /* Set curve types. */
369  MutableSpan<int8_t> types_span = curves.curve_types_for_write();
370  types_span.drop_front(old_curves_num).fill(CURVE_TYPE_CATMULL_ROM);
371  curves.update_curve_types();
372 
373  return outputs;
374 }
375 
376 } // namespace blender::geometry
typedef float(TangentPoint)[2]
#define BLI_assert(a)
Definition: BLI_assert.h:46
void mul_m3_v3(const float M[3][3], float r[3])
Definition: math_matrix.c:926
void rotation_between_vecs_to_mat3(float m[3][3], const float v1[3], const float v2[3])
@ CURVE_TYPE_CATMULL_ROM
struct CurvesGeometry CurvesGeometry
Group Output data from inside of a node group A color picker Mix two input colors RGB to Convert a color s luminance to a grayscale value Generate a normal vector and a dot product Bright Control the brightness and contrast of the input color Vector Map an input vectors to curves
const T & last(const int64_t n=0) const
Definition: BLI_array.hh:284
IndexRange index_range() const
Definition: BLI_array.hh:348
constexpr int64_t size() const
constexpr int64_t size() const
Definition: BLI_span.hh:511
constexpr void fill(const T &value)
Definition: BLI_span.hh:527
constexpr MutableSpan slice(const int64_t start, const int64_t size) const
Definition: BLI_span.hh:581
constexpr MutableSpan take_back(const int64_t n) const
Definition: BLI_span.hh:631
constexpr void copy_from(Span< T > values)
Definition: BLI_span.hh:707
constexpr IndexRange index_range() const
Definition: BLI_span.hh:661
constexpr int64_t size() const
Definition: BLI_span.hh:240
int64_t size() const
Definition: BLI_vector.hh:694
void append(const T &value)
Definition: BLI_vector.hh:433
bool is_empty() const
Definition: BLI_vector.hh:706
Result sample(const float2 &query_uv) const
IconTextureDrawCall normal
ccl_gpu_kernel_postfix int ccl_global int * indices
#define T
typename DefaultMixerStruct< T >::type DefaultMixer
T mix3(const float3 &weights, const T &v0, const T &v1, const T &v2)
int segments_num(const int points_num, const bool cyclic)
Definition: BKE_curves.hh:462
static Array< NeighborCurves > find_curve_neighbors(const Span< float3 > root_positions, const KDTree_3d &old_roots_kdtree)
float3 compute_surface_point_normal(const MLoopTri &looptri, const float3 &bary_coord, const Span< float3 > corner_normals)
AddCurvesOnMeshOutputs add_curves_on_mesh(bke::CurvesGeometry &curves, const AddCurvesOnMeshInputs &inputs)
static void interpolate_position_without_interpolation(CurvesGeometry &curves, const int old_curves_num, const Span< float3 > root_positions_cu, const Span< float > new_lengths_cu, const Span< float3 > new_normals_su, const float4x4 &surface_to_curves_normal_mat)
static void initialize_straight_curve_positions(const float3 &p1, const float3 &p2, MutableSpan< float3 > r_positions)
static void interpolate_position_with_interpolation(CurvesGeometry &curves, const Span< float3 > root_positions_cu, const Span< NeighborCurves > neighbors_per_curve, const int old_curves_num, const Span< float > new_lengths_cu, const Span< float3 > new_normals_su, const bke::CurvesSurfaceTransforms &transforms, const ReverseUVSampler &reverse_uv_sampler, const Span< float3 > corner_normals_su)
static constexpr int max_neighbors
void interpolate_from_neighbors(const Span< NeighborCurves > neighbors_per_curve, const T &fallback, const GetValueF &get_value_from_neighbor, MutableSpan< T > r_interpolated_values)
void sample_at_lengths(Span< float > accumulated_segment_lengths, Span< float > sample_lengths, MutableSpan< int > r_segment_indices, MutableSpan< float > r_factors)
void interpolate(const Span< T > src, const Span< int > indices, const Span< float > factors, MutableSpan< T > dst)
T length(const vec_base< T, Size > &a)
vec_base< T, Size > normalize(const vec_base< T, Size > &v)
T interpolate(const T &a, const T &b, const FactorT &t)
void parallel_for(IndexRange range, int64_t grain_size, const Function &function)
Definition: BLI_task.hh:51
static bNodeSocketTemplate outputs[]
static bNodeSocketTemplate inputs[]
#define min(a, b)
Definition: sort.c:35
unsigned int tri[3]
float max