Blender V5.3
node_geo_interpolate_curves.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
6
7#include "BLI_math_vector.hh"
8
9#include "BLI_kdtree_new.hh"
13#include "BLI_task.hh"
14
15#include "BKE_curves.hh"
16
18
19#include "GEO_randomize.hh"
20
22
24{
25 b.add_input<decl::Geometry>("Guide Curves"_ustr)
26 .description("Base curves that new curves are interpolated between");
27 b.add_input<decl::Vector>("Guide Up"_ustr)
28 .evaluated_geometry_field({0})
29 .hide_value()
30 .description("Optional up vector that is typically a surface normal");
31 b.add_input<decl::Int>("Guide Group ID"_ustr)
32 .evaluated_geometry_field({0})
33 .hide_value()
35 "Splits guides into separate groups. New curves interpolate existing curves "
36 "from a single group");
37 b.add_input<decl::Geometry>("Points"_ustr)
38 .description("First control point positions for new interpolated curves");
39 b.add_input<decl::Vector>("Point Up"_ustr)
40 .evaluated_geometry_field({3})
41 .hide_value()
42 .description("Optional up vector that is typically a surface normal");
43 b.add_input<decl::Int>("Point Group ID"_ustr)
44 .evaluated_geometry_field({3})
45 .hide_value()
46 .description("The curve group to interpolate in");
47 b.add_input<decl::Int>("Max Neighbors"_ustr)
48 .default_value(4)
49 .min(1)
51 "Maximum amount of close guide curves that are taken into account for interpolation");
52 b.add_output<decl::Geometry>("Curves"_ustr).propagate_all_geometry();
53 b.add_output<decl::Int>("Closest Index"_ustr)
54 .anonymous_attribute_output()
55 .description("Index of the closest guide curve for each generated curve");
56 b.add_output<decl::Float>("Closest Weight"_ustr)
57 .anonymous_attribute_output()
58 .description("Weight of the closest guide curve for each generated curve");
59}
60
66 const bke::CurvesGeometry &guide_curves)
67{
68 const OffsetIndices points_by_curve = guide_curves.points_by_curve();
69 /* Indexed by group; -1 means the curves in that group don't all have the same point count. */
70 Array<int> points_per_curve_by_group(guides_by_group.size());
71 for (const int group : guides_by_group.index_range()) {
72 const Span<int> guide_curve_indices = guides_by_group[group];
73 int group_control_points = points_by_curve[guide_curve_indices[0]].size();
74 for (const int guide_curve_i : guide_curve_indices.drop_front(1)) {
75 const int control_points = points_by_curve[guide_curve_i].size();
76 if (group_control_points != control_points) {
77 group_control_points = -1;
78 break;
79 }
80 }
81 points_per_curve_by_group[group] = group_control_points;
82 }
83 return points_per_curve_by_group;
84}
85
90 const GroupedSpan<int> guides_by_group, const Span<float3> root_positions)
91{
92 Array<std::unique_ptr<KDTreeNew<float3>>> kdtrees(guides_by_group.size());
94 guides_by_group.index_range(),
95 1024,
96 [&](const IndexRange range) {
97 for (const int group : range) {
98 kdtrees[group] = std::make_unique<KDTreeNew<float3>>(root_positions,
99 guides_by_group[group]);
100 }
101 },
103 [&](const IndexRange range) { return guides_by_group.offsets[range].size(); }));
104
105 return kdtrees;
106}
107
112static void find_neighbor_guides(const Span<float3> positions,
113 const Span<int> point_group_indices,
114 const Span<std::unique_ptr<KDTreeNew<float3>>> kdtrees,
115 const GroupedSpan<int> guides_by_group,
116 const int max_neighbor_count,
117 MutableSpan<int> r_all_neighbor_indices,
118 MutableSpan<float> r_all_neighbor_weights,
119 MutableSpan<int> r_all_neighbor_counts)
120{
121 threading::parallel_for(positions.index_range(), 128, [&](const IndexRange range) {
122 for (const int child_curve_i : range) {
123 const float3 &position = positions[child_curve_i];
124 const int group = point_group_indices[child_curve_i];
125 if (group == -1) {
126 r_all_neighbor_counts[child_curve_i] = 0;
127 continue;
128 }
129 const KDTreeNew<float3> &kdtree = *kdtrees[group];
130
131 const int num_guides_in_group = guides_by_group[group].size();
132 /* Finding an additional neighbor that currently has weight zero is necessary to ensure that
133 * curves close by but with different guides still look similar. Otherwise there can be
134 * visible artifacts. */
135 const bool use_extra_neighbor = num_guides_in_group > max_neighbor_count;
136 const int neighbors_to_find = max_neighbor_count + use_extra_neighbor;
137
138 Vector<KDTreeNew<float3>::Nearest, 16> nearest_n(neighbors_to_find);
139 const int num_neighbors = kdtree.find_nearest_n(position, nearest_n);
140 if (num_neighbors == 0) {
141 r_all_neighbor_counts[child_curve_i] = 0;
142 continue;
143 }
144
145 const IndexRange neighbors_range{child_curve_i * max_neighbor_count, max_neighbor_count};
146 MutableSpan<int> neighbor_indices = r_all_neighbor_indices.slice(neighbors_range);
147 MutableSpan<float> neighbor_weights = r_all_neighbor_weights.slice(neighbors_range);
148
149 float tot_weight = 0.0f;
150 /* A different weighting algorithm is necessary for smooth transitions when desired. */
151 if (use_extra_neighbor) {
152 /* Find the distance to the guide with the largest distance. At this distance, the weight
153 * should become zero. */
154 const float max_distance = math::sqrt(
155 std::max_element(
156 nearest_n.begin(),
157 nearest_n.begin() + num_neighbors,
158 [](const KDTreeNew<float3>::Nearest &a, const KDTreeNew<float3>::Nearest &b) {
159 return a.distance_sq < b.distance_sq;
160 })
161 ->distance_sq);
162 if (max_distance == 0.0f) {
163 r_all_neighbor_counts[child_curve_i] = 1;
164 neighbor_indices[0] = nearest_n[0].index;
165 neighbor_weights[0] = 1.0f;
166 continue;
167 }
168
169 int neighbor_counter = 0;
170 for (const int neighbor_i : IndexRange(num_neighbors)) {
171 const KDTreeNew<float3>::Nearest &nearest = nearest_n[neighbor_i];
172 const float dist = math::sqrt(nearest.distance_sq);
173 /* Goal for this weight calculation:
174 * - As distance gets closer to zero, it should become very large.
175 * - At `max_distance` the weight should be zero. */
176 const float weight = (max_distance - dist) / std::max(dist, 0.000001f);
177 if (weight > 0.0f) {
178 tot_weight += weight;
179 neighbor_indices[neighbor_counter] = nearest.index;
180 neighbor_weights[neighbor_counter] = weight;
181 neighbor_counter++;
182 }
183 }
184 r_all_neighbor_counts[child_curve_i] = neighbor_counter;
185 }
186 else {
187 int neighbor_counter = 0;
188 for (const int neighbor_i : IndexRange(num_neighbors)) {
189 const KDTreeNew<float3>::Nearest &nearest = nearest_n[neighbor_i];
190 const float dist = math::sqrt(nearest.distance_sq);
191 /* Goal for this weight calculation:
192 * - As the distance gets closer to zero, it should become very large.
193 * - As the distance gets larger, the weight should become zero. */
194 const float weight = 1.0f / std::max(dist, 0.000001f);
195 if (weight > 0.0f) {
196 tot_weight += weight;
197 neighbor_indices[neighbor_counter] = nearest.index;
198 neighbor_weights[neighbor_counter] = weight;
199 neighbor_counter++;
200 }
201 }
202 r_all_neighbor_counts[child_curve_i] = neighbor_counter;
203 }
204 if (tot_weight > 0.0f) {
205 /* Normalize weights so that their sum is 1. */
206 const float weight_factor = 1.0f / tot_weight;
207 for (float &weight : neighbor_weights.take_front(r_all_neighbor_counts[child_curve_i])) {
208 weight *= weight_factor;
209 }
210 }
211 }
212 });
213}
214
220 const Span<int> point_group_indices,
221 const Span<int> points_per_curve_by_group,
222 const Span<int> all_neighbor_indices,
223 const Span<float> all_neighbor_weights,
224 const Span<int> all_neighbor_counts,
225 const int max_neighbors,
226 MutableSpan<int> r_points_per_child,
227 MutableSpan<bool> r_use_direct_interpolation)
228{
229 const OffsetIndices guide_points_by_curve = guide_curves.points_by_curve();
230 threading::parallel_for(r_points_per_child.index_range(), 512, [&](const IndexRange range) {
231 for (const int child_curve_i : range) {
232 const int neighbor_count = all_neighbor_counts[child_curve_i];
233 if (neighbor_count == 0) {
234 r_points_per_child[child_curve_i] = 1;
235 r_use_direct_interpolation[child_curve_i] = false;
236 continue;
237 }
238 const int group = point_group_indices[child_curve_i];
239 const int points_per_curve_in_group = points_per_curve_by_group[group];
240 if (points_per_curve_in_group != -1) {
241 r_points_per_child[child_curve_i] = points_per_curve_in_group;
242 r_use_direct_interpolation[child_curve_i] = true;
243 continue;
244 }
245 const IndexRange neighbors_range{child_curve_i * max_neighbors, neighbor_count};
246 const Span<float> neighbor_weights = all_neighbor_weights.slice(neighbors_range);
247 const Span<int> neighbor_indices = all_neighbor_indices.slice(neighbors_range);
248
249 float neighbor_points_weighted_sum = 0.0f;
250 for (const int neighbor_i : IndexRange(neighbor_count)) {
251 const int neighbor_index = neighbor_indices[neighbor_i];
252 const float neighbor_weight = neighbor_weights[neighbor_i];
253 const int neighbor_points = guide_points_by_curve[neighbor_index].size();
254 neighbor_points_weighted_sum += neighbor_weight * float(neighbor_points);
255 }
256 const int points_in_child = std::max<int>(1, roundf(neighbor_points_weighted_sum));
257 r_points_per_child[child_curve_i] = points_in_child;
258 r_use_direct_interpolation[child_curve_i] = false;
259 }
260 });
261}
262
266static void parameterize_guide_curves(const bke::CurvesGeometry &guide_curves,
267 Array<int> &r_parameterized_guide_offsets,
268 Array<float> &r_parameterized_guide_lengths)
269{
270 r_parameterized_guide_offsets.reinitialize(guide_curves.curves_num() + 1);
271 const OffsetIndices guide_points_by_curve = guide_curves.points_by_curve();
272 threading::parallel_for(guide_curves.curves_range(), 1024, [&](const IndexRange range) {
273 for (const int guide_curve_i : range) {
274 r_parameterized_guide_offsets[guide_curve_i] = length_parameterize::segments_num(
275 guide_points_by_curve[guide_curve_i].size(), false);
276 }
277 });
278 offset_indices::accumulate_counts_to_offsets(r_parameterized_guide_offsets);
279 const OffsetIndices<int> parameterize_offsets{r_parameterized_guide_offsets};
280
281 r_parameterized_guide_lengths.reinitialize(r_parameterized_guide_offsets.last());
282 const Span<float3> guide_positions = guide_curves.positions();
283 threading::parallel_for(guide_curves.curves_range(), 256, [&](const IndexRange range) {
284 for (const int guide_curve_i : range) {
285 const IndexRange points = guide_points_by_curve[guide_curve_i];
286 const IndexRange lengths_range = parameterize_offsets[guide_curve_i];
287 length_parameterize::accumulate_lengths<float3>(
288 guide_positions.slice(points),
289 false,
290 r_parameterized_guide_lengths.as_mutable_span().slice(lengths_range));
291 }
292 });
293}
294
299 const bke::CurvesGeometry &guide_curves,
300 const int max_neighbors,
301 const Span<int> all_neighbor_indices,
302 const Span<float> all_neighbor_weights,
303 const Span<int> all_neighbor_counts,
304 const VArray<float3> &guides_up,
305 const VArray<float3> &points_up,
306 const Span<float3> point_positions,
307 const OffsetIndices<int> parameterized_guide_offsets,
308 const Span<float> parameterized_guide_lengths,
309 const Span<bool> use_direct_interpolation_per_child)
310{
311 const OffsetIndices guide_points_by_curve = guide_curves.points_by_curve();
312 const OffsetIndices child_points_by_curve = child_curves.points_by_curve();
313 const MutableSpan<float3> children_positions = child_curves.positions_for_write();
314 const Span<float3> guide_positions = guide_curves.positions();
315
316 threading::parallel_for(child_curves.curves_range(), 128, [&](const IndexRange range) {
317 Vector<float, 16> sample_lengths;
318 Vector<int, 16> sample_segments;
319 Vector<float, 16> sample_factors;
320
321 for (const int child_curve_i : range) {
322 const IndexRange points = child_points_by_curve[child_curve_i];
323 const int neighbor_count = all_neighbor_counts[child_curve_i];
324 const float3 child_up = points_up[child_curve_i];
325 BLI_assert(math::is_unit_scale(child_up));
326 const float3 &child_root_position = point_positions[child_curve_i];
327 MutableSpan<float3> child_positions = children_positions.slice(points);
328
329 child_positions.fill(child_root_position);
330 if (neighbor_count == 0) {
331 /* Creates a curve with a single point at the root position. */
332 continue;
333 }
334
335 const IndexRange neighbors_range{child_curve_i * max_neighbors, neighbor_count};
336 const Span<float> neighbor_weights = all_neighbor_weights.slice(neighbors_range);
337 const Span<int> neighbor_indices = all_neighbor_indices.slice(neighbors_range);
338
339 const bool use_direct_interpolation = use_direct_interpolation_per_child[child_curve_i];
340
341 for (const int neighbor_i : IndexRange(neighbor_count)) {
342 const int neighbor_index = neighbor_indices[neighbor_i];
343 const float neighbor_weight = neighbor_weights[neighbor_i];
344 const IndexRange guide_points = guide_points_by_curve[neighbor_index];
345 const Span<float3> neighbor_positions = guide_positions.slice(guide_points);
346 const float3 &neighbor_root = neighbor_positions.first();
347 const float3 neighbor_up = guides_up[neighbor_index];
348 BLI_assert(math::is_unit_scale(neighbor_up));
349
350 const bool is_same_up_vector = neighbor_up == child_up;
351
352 float3x3 normal_rotation;
353 if (!is_same_up_vector) {
354 rotation_between_vecs_to_mat3(normal_rotation.ptr(), neighbor_up, child_up);
355 }
356
357 if (use_direct_interpolation) {
358 /* In this method, the control point positions are interpolated directly instead of
359 * looking at evaluated points. This is much faster than the method below but only works
360 * if all guides have the same number of points. */
361 for (const int i : IndexRange(points.size())) {
362 const float3 &neighbor_pos = neighbor_positions[i];
363 const float3 relative_to_root = neighbor_pos - neighbor_root;
364 float3 rotated_relative = relative_to_root;
365 if (!is_same_up_vector) {
366 rotated_relative = normal_rotation * rotated_relative;
367 }
368 child_positions[i] += neighbor_weight * rotated_relative;
369 }
370 }
371 else {
372 /* This method is used when guide curves have different amounts of control points. In
373 * this case, some additional interpolation is necessary compared to the method above. */
374
375 const IndexRange guide_offsets = parameterized_guide_offsets[neighbor_index];
376
377 if (guide_offsets.is_empty()) {
378 /* Single point curve. */
379 float3 rotated_relative = neighbor_root;
380 if (!is_same_up_vector) {
381 rotated_relative = normal_rotation * rotated_relative;
382 }
383 const float3 global_pos = rotated_relative * neighbor_weight;
384 for (float3 &position : child_positions) {
385 position += global_pos;
386 }
387 continue;
388 }
389
390 const Span<float> lengths = parameterized_guide_lengths.slice(guide_offsets);
391 const float neighbor_length = lengths.last();
392
393 sample_lengths.reinitialize(points.size());
394 const float sample_length_factor = math::safe_divide(neighbor_length,
395 float(points.size() - 1));
396 for (const int i : sample_lengths.index_range()) {
397 sample_lengths[i] = i * sample_length_factor;
398 }
399
400 sample_segments.reinitialize(points.size());
401 sample_factors.reinitialize(points.size());
402 length_parameterize::sample_at_lengths(
403 lengths, sample_lengths, sample_segments, sample_factors);
404
405 for (const int i : IndexRange(points.size())) {
406 const int segment = sample_segments[i];
407 const float factor = sample_factors[i];
408 const float3 sample_pos = math::interpolate(
409 neighbor_positions[segment], neighbor_positions[segment + 1], factor);
410 const float3 relative_to_root = sample_pos - neighbor_root;
411 float3 rotated_relative = relative_to_root;
412 if (!is_same_up_vector) {
413 rotated_relative = normal_rotation * rotated_relative;
414 }
415 child_positions[i] += neighbor_weight * rotated_relative;
416 }
417 }
418 }
419 }
420 });
421
422 /* Can only create catmull rom curves for now. */
423 child_curves.fill_curve_types(CURVE_TYPE_CATMULL_ROM);
424}
425
430 const bke::CurvesGeometry &guide_curves,
431 const AttributeAccessor &point_attributes,
432 const AttributeFilter &attribute_filter,
433 const int max_neighbors,
434 const Span<int> all_neighbor_indices,
435 const Span<float> all_neighbor_weights,
436 const Span<int> all_neighbor_counts,
437 const OffsetIndices<int> parameterized_guide_offsets,
438 const Span<float> parameterized_guide_lengths,
439 const Span<bool> use_direct_interpolation_per_child)
440{
441 const AttributeAccessor guide_curve_attributes = guide_curves.attributes();
442 MutableAttributeAccessor children_attributes = child_curves.attributes_for_write();
443
444 const OffsetIndices child_points_by_curve = child_curves.points_by_curve();
445 const OffsetIndices guide_points_by_curve = guide_curves.points_by_curve();
446
447 /* Interpolate attributes from guide curves to child curves. Attributes stay on the same domain
448 * that they had on the guides. */
449 guide_curve_attributes.foreach_attribute([&](const bke::AttributeIter &iter) {
450 if (attribute_filter.allow_skip(iter.name)) {
451 return;
452 }
453 const bke::AttrType type = iter.data_type;
454 if (type == bke::AttrType::String) {
455 return;
456 }
457 if (iter.is_builtin && !ELEM(iter.name, "radius", "tilt", "resolution", "cyclic")) {
458 return;
459 }
460
461 const GVArray src_attr = *iter.get();
462 const CommonVArrayInfo info = src_attr.common_info();
464 const GPointer value(src_attr.type(), info.data);
465 if (children_attributes.add(iter.name, iter.domain, type, bke::AttributeInitValue(value))) {
466 return;
467 }
468 }
469
470 const GVArraySpan src_generic = src_attr;
471
472 if (iter.domain == AttrDomain::Curve) {
473 GSpanAttributeWriter dst_generic = children_attributes.lookup_or_add_for_write_only_span(
474 iter.name, AttrDomain::Curve, type);
475 if (!dst_generic) {
476 return;
477 }
478 bke::attribute_math::to_static_type(type, [&]<typename T>() {
479 if constexpr (!std::is_void_v<bke::attribute_math::DefaultMixer<T>>) {
480 const Span<T> src = src_generic.typed<T>();
481 MutableSpan<T> dst = dst_generic.span.typed<T>();
482
483 threading::parallel_for(child_curves.curves_range(), 256, [&](const IndexRange range) {
484 for (const int child_curve_i : range) {
485 const int neighbor_count = all_neighbor_counts[child_curve_i];
486 const IndexRange neighbors_range{child_curve_i * max_neighbors, neighbor_count};
487 dst[child_curve_i] = bke::attribute_math::mix_indices(
488 src,
489 all_neighbor_indices.slice(neighbors_range),
490 all_neighbor_weights.slice(neighbors_range));
491 }
492 });
493 }
494 });
495
496 dst_generic.finish();
497 }
498 else {
499 BLI_assert(iter.domain == AttrDomain::Point);
500 GSpanAttributeWriter dst_generic = children_attributes.lookup_or_add_for_write_only_span(
501 iter.name, AttrDomain::Point, type);
502 if (!dst_generic) {
503 return;
504 }
505
506 bke::attribute_math::to_static_type(type, [&]<typename T>() {
507 if constexpr (!std::is_void_v<bke::attribute_math::DefaultMixer<T>>) {
508 const Span<T> src = src_generic.typed<T>();
509 MutableSpan<T> dst = dst_generic.span.typed<T>();
510
512 threading::parallel_for(child_curves.curves_range(), 256, [&](const IndexRange range) {
513 Vector<float, 16> sample_lengths;
514 Vector<int, 16> sample_segments;
515 Vector<float, 16> sample_factors;
516 for (const int child_curve_i : range) {
517 const IndexRange points = child_points_by_curve[child_curve_i];
518 const int neighbor_count = all_neighbor_counts[child_curve_i];
519 const IndexRange neighbors_range{child_curve_i * max_neighbors, neighbor_count};
520 const Span<float> neighbor_weights = all_neighbor_weights.slice(neighbors_range);
521 const Span<int> neighbor_indices = all_neighbor_indices.slice(neighbors_range);
522 const bool use_direct_interpolation =
523 use_direct_interpolation_per_child[child_curve_i];
524
525 for (const int neighbor_i : IndexRange(neighbor_count)) {
526 const int neighbor_index = neighbor_indices[neighbor_i];
527 const float neighbor_weight = neighbor_weights[neighbor_i];
528 const IndexRange guide_points = guide_points_by_curve[neighbor_index];
529
530 if (use_direct_interpolation) {
531 for (const int i : IndexRange(points.size())) {
532 mixer.mix_in(points[i], src[guide_points[i]], neighbor_weight);
533 }
534 }
535 else {
536 const IndexRange guide_offsets = parameterized_guide_offsets[neighbor_index];
537 if (guide_offsets.is_empty()) {
538 /* Single point curve. */
539 const T &curve_value = src[guide_points.first()];
540 for (const int i : points) {
541 mixer.mix_in(i, curve_value, neighbor_weight);
542 }
543 continue;
544 }
545
546 const Span<float> lengths = parameterized_guide_lengths.slice(guide_offsets);
547 const float neighbor_length = lengths.last();
548
549 sample_lengths.reinitialize(points.size());
550 const float sample_length_factor = math::safe_divide(neighbor_length,
551 float(points.size() - 1));
552 for (const int i : sample_lengths.index_range()) {
553 sample_lengths[i] = i * sample_length_factor;
554 }
555
556 sample_segments.reinitialize(points.size());
557 sample_factors.reinitialize(points.size());
558 length_parameterize::sample_at_lengths(
559 lengths, sample_lengths, sample_segments, sample_factors);
560
561 for (const int i : IndexRange(points.size())) {
562 const int segment = sample_segments[i];
563 const float factor = sample_factors[i];
564 const T value = math::interpolate(
565 src[guide_points[segment]], src[guide_points[segment + 1]], factor);
566 mixer.mix_in(points[i], value, neighbor_weight);
567 }
568 }
569 }
570 }
571 mixer.finalize(child_points_by_curve[range]);
572 });
573 }
574 });
575
576 dst_generic.finish();
577 }
578 });
579
580 /* Interpolate attributes from the points to child curves. All attributes become curve
581 * attributes. */
582 point_attributes.foreach_attribute([&](const bke::AttributeIter &iter) {
583 if (iter.is_builtin && !children_attributes.is_builtin(iter.name)) {
584 return;
585 }
586 if (guide_curve_attributes.contains(iter.name)) {
587 return;
588 }
589 if (attribute_filter.allow_skip(iter.name)) {
590 return;
591 }
592 if (iter.data_type == bke::AttrType::String) {
593 return;
594 }
595
596 const GAttributeReader src = iter.get();
597 if (src.sharing_info && src.varray.is_span()) {
598 const bke::AttributeInitShared init(src.varray.get_internal_span().data(),
599 *src.sharing_info);
600 children_attributes.add(iter.name, AttrDomain::Curve, iter.data_type, init);
601 }
602 else {
603 children_attributes.add(
604 iter.name, AttrDomain::Curve, iter.data_type, bke::AttributeInitVArray(src.varray));
605 }
606 });
607}
608
610 const std::optional<StringRef> &weight_attribute_id,
611 const std::optional<StringRef> &index_attribute_id,
612 const int max_neighbors,
613 const Span<int> all_neighbor_counts,
614 const Span<int> all_neighbor_indices,
615 const Span<float> all_neighbor_weights)
616{
617 if (!weight_attribute_id && !index_attribute_id) {
618 return;
619 }
620 SpanAttributeWriter<float> weight_attribute;
621 if (weight_attribute_id) {
622 weight_attribute =
624 *weight_attribute_id, AttrDomain::Curve);
625 }
626 SpanAttributeWriter<int> index_attribute;
627 if (index_attribute_id) {
628 index_attribute = child_curves.attributes_for_write().lookup_or_add_for_write_only_span<int>(
629 *index_attribute_id, AttrDomain::Curve);
630 }
631 threading::parallel_for(child_curves.curves_range(), 512, [&](const IndexRange range) {
632 for (const int child_curve_i : range) {
633 const int neighbor_count = all_neighbor_counts[child_curve_i];
634
635 int closest_index;
636 float closest_weight;
637 if (neighbor_count == 0) {
638 closest_index = 0;
639 closest_weight = 0.0f;
640 }
641 else {
642 const IndexRange neighbors_range{child_curve_i * max_neighbors, neighbor_count};
643 const Span<float> neighbor_weights = all_neighbor_weights.slice(neighbors_range);
644 const Span<int> neighbor_indices = all_neighbor_indices.slice(neighbors_range);
645 const int max_index = std::max_element(neighbor_weights.begin(), neighbor_weights.end()) -
646 neighbor_weights.begin();
647 closest_index = neighbor_indices[max_index];
648 closest_weight = neighbor_weights[max_index];
649 }
650 if (index_attribute) {
651 index_attribute.span[child_curve_i] = closest_index;
652 }
653 if (weight_attribute) {
654 weight_attribute.span[child_curve_i] = closest_weight;
655 }
656 }
657 });
658 if (index_attribute) {
659 index_attribute.finish();
660 }
661 if (weight_attribute) {
662 weight_attribute.finish();
663 }
664}
665
667 const Curves &guide_curves_id,
668 const AttributeAccessor &point_attributes,
669 const VArray<float3> &guides_up,
670 const VArray<float3> &points_up,
671 const Span<int> guide_group_ids,
672 const VArray<int> &point_group_ids,
673 const int max_neighbors,
674 const AttributeFilter &attribute_filter,
675 const std::optional<StringRef> &index_attribute_id,
676 const std::optional<StringRef> &weight_attribute_id)
677{
678 const bke::CurvesGeometry &guide_curves = guide_curves_id.geometry.wrap();
679
680 /* Guides are split into groups. Every point will only interpolate between guides within the
681 * group with the same id. Groups are identified by an arbitrary id, which is first translated
682 * into a compact index that can be used for array lookups. */
683 const VectorSet<int> guide_group_indexing(guide_group_ids);
684
685 Array<int> guide_group_indices(guide_group_ids.size());
686 threading::parallel_for(guide_group_ids.index_range(), 4096, [&](const IndexRange range) {
687 for (const int i : range) {
688 guide_group_indices[i] = guide_group_indexing.index_of(guide_group_ids[i]);
689 }
690 });
691
692 Array<int> group_offset_data;
693 Array<int> group_index_data;
695 guide_group_indices, guide_group_indexing.size(), group_offset_data, group_index_data);
696
697 const Array<int> points_per_curve_by_group = compute_points_per_curve_by_group(guides_by_group,
698 guide_curves);
699
700 Array<float3> root_positions(guide_curves.curves_num());
701 array_utils::gather(guide_curves.positions(),
702 guide_curves.offsets().take_front(guide_curves.curves_num()),
703 root_positions.as_mutable_span());
704
705 Array<std::unique_ptr<KDTreeNew<float3>>> kdtrees = build_kdtrees_for_root_positions(
706 guides_by_group, root_positions);
707
708 const VArraySpan point_positions = *point_attributes.lookup<float3>("position");
709 const int num_child_curves = point_attributes.domain_size(AttrDomain::Point);
710
711 /* Points may reference a group id that no guide belongs to, in which case there are no
712 * neighbors to interpolate from. */
713 Array<int> point_group_indices(num_child_curves);
714 threading::parallel_for(IndexRange(num_child_curves), 4096, [&](const IndexRange range) {
715 for (const int i : range) {
716 point_group_indices[i] = int(guide_group_indexing.index_of_try(point_group_ids[i]));
717 }
718 });
719
720 /* The set of guides per child are stored in a flattened array to allow fast access, reduce
721 * memory consumption and reduce number of allocations. */
722 Array<int> all_neighbor_indices(num_child_curves * max_neighbors);
723 Array<float> all_neighbor_weights(num_child_curves * max_neighbors);
724 Array<int> all_neighbor_counts(num_child_curves);
725
726 find_neighbor_guides(point_positions,
727 point_group_indices,
728 kdtrees,
729 guides_by_group,
730 max_neighbors,
731 all_neighbor_indices,
732 all_neighbor_weights,
733 all_neighbor_counts);
734
735 Curves *child_curves_id = bke::curves_new_nomain(0, num_child_curves);
736 bke::CurvesGeometry &child_curves = child_curves_id->geometry.wrap();
737 MutableSpan<int> children_curve_offsets = child_curves.offsets_for_write();
738
739 Array<bool> use_direct_interpolation_per_child(num_child_curves);
740 compute_point_counts_per_child(guide_curves,
741 point_group_indices,
742 points_per_curve_by_group,
743 all_neighbor_indices,
744 all_neighbor_weights,
745 all_neighbor_counts,
746 max_neighbors,
747 children_curve_offsets.drop_back(1),
748 use_direct_interpolation_per_child);
749 offset_indices::accumulate_counts_to_offsets(children_curve_offsets);
750 const int num_child_points = children_curve_offsets.last();
751 child_curves.resize(num_child_points, num_child_curves);
752
753 /* Stores parameterization of all guide curves in flat arrays. */
754 Array<int> parameterized_guide_offsets;
755 Array<float> parameterized_guide_lengths;
756 parameterize_guide_curves(
757 guide_curves, parameterized_guide_offsets, parameterized_guide_lengths);
758
759 interpolate_curve_shapes(child_curves,
760 guide_curves,
761 max_neighbors,
762 all_neighbor_indices,
763 all_neighbor_weights,
764 all_neighbor_counts,
765 guides_up,
766 points_up,
767 point_positions,
768 OffsetIndices<int>(parameterized_guide_offsets),
769 parameterized_guide_lengths,
770 use_direct_interpolation_per_child);
771 interpolate_curve_attributes(child_curves,
772 guide_curves,
773 point_attributes,
774 attribute_filter,
775 max_neighbors,
776 all_neighbor_indices,
777 all_neighbor_weights,
778 all_neighbor_counts,
779 OffsetIndices<int>(parameterized_guide_offsets),
780 parameterized_guide_lengths,
781 use_direct_interpolation_per_child);
782
783 store_output_attributes(child_curves,
784 weight_attribute_id,
785 index_attribute_id,
786 max_neighbors,
787 all_neighbor_counts,
788 all_neighbor_indices,
789 all_neighbor_weights);
790
791 if (guide_curves_id.mat != nullptr) {
792 child_curves_id->mat = MEM_dupalloc(guide_curves_id.mat);
793 child_curves_id->totcol = guide_curves_id.totcol;
794 }
795
796 geometry::debug_randomize_curve_order(&child_curves);
797
798 return GeometrySet::from_curves(child_curves_id);
799}
800
802{
803 GeometrySet guide_curves_geometry = params.extract_input<GeometrySet>("Guide Curves"_ustr);
804 const GeometrySet points_geometry = params.extract_input<GeometrySet>("Points"_ustr);
805
806 if (!guide_curves_geometry.has_curves() ||
807 guide_curves_geometry.get_curves()->geometry.curve_num == 0)
808 {
810 return;
811 }
812 const GeometryComponent *points_component = points_geometry.get_component<PointCloudComponent>();
813 if (points_component == nullptr) {
814 points_component = points_geometry.get_component<MeshComponent>();
815 }
816 if (points_component == nullptr || points_geometry.is_empty()) {
818 return;
819 }
820
821 const int max_neighbors = std::max<int>(1, params.extract_input<int>("Max Neighbors"_ustr));
822
823 static const mf::MultiFunction &normalize_fn = fn::multi_function::registry::lookup(
824 "normalize(float3)"_ustr);
825
826 /* Normalize up fields so that is done as part of field evaluation. */
827 Field<float3> guides_up_field(
828 FieldOperation::from(normalize_fn, {params.extract_input<Field<float3>>("Guide Up"_ustr)}));
829 Field<float3> points_up_field(
830 FieldOperation::from(normalize_fn, {params.extract_input<Field<float3>>("Point Up"_ustr)}));
831
832 Field<int> guide_group_field = params.extract_input<Field<int>>("Guide Group ID"_ustr);
833 Field<int> point_group_field = params.extract_input<Field<int>>("Point Group ID"_ustr);
834
835 const Curves &guide_curves_id = *guide_curves_geometry.get_curves();
836
837 const bke::CurvesFieldContext curves_context{guide_curves_id, AttrDomain::Curve};
838 fn::FieldEvaluator curves_evaluator{curves_context, guide_curves_id.geometry.curve_num};
839 curves_evaluator.add(guides_up_field);
840 curves_evaluator.add(guide_group_field);
841 curves_evaluator.evaluate();
842 const VArray<float3> guides_up = curves_evaluator.get_evaluated<float3>(0);
843 const VArraySpan<int> guide_group_ids = curves_evaluator.get_evaluated<int>(1);
844
845 const bke::GeometryFieldContext points_context(*points_component, AttrDomain::Point);
846 fn::FieldEvaluator points_evaluator{points_context,
847 points_component->attribute_domain_size(AttrDomain::Point)};
848 points_evaluator.add(points_up_field);
849 points_evaluator.add(point_group_field);
850 points_evaluator.evaluate();
851 const VArray<float3> points_up = points_evaluator.get_evaluated<float3>(0);
852 const VArray<int> point_group_ids = points_evaluator.get_evaluated<int>(1);
853
854 const NodeAttributeFilter &attribute_filter = params.get_attribute_filter("Curves"_ustr);
855
856 std::optional<std::string> index_attribute_id =
857 params.get_output_anonymous_attribute_id_if_needed("Closest Index"_ustr);
858 std::optional<std::string> weight_attribute_id =
859 params.get_output_anonymous_attribute_id_if_needed("Closest Weight"_ustr);
860
861 GeometrySet new_curves = generate_interpolated_curves(guide_curves_id,
862 *points_component->attributes(),
863 guides_up,
864 points_up,
865 guide_group_ids,
866 point_group_ids,
867 max_neighbors,
868 attribute_filter,
869 index_attribute_id,
870 weight_attribute_id);
871
873 if (const auto *curve_edit_data =
874 guide_curves_geometry.get_component<GeometryComponentEditData>())
875 {
876 new_curves.add(*curve_edit_data);
877 }
878 new_curves.set_name(guide_curves_geometry.name());
879 new_curves.copy_bundle_from(guide_curves_geometry);
880
881 params.set_output("Curves"_ustr, std::move(new_curves));
882}
883
884static void node_register()
885{
886 static bke::bNodeType ntype;
887
888 geo_node_type_base(&ntype, "GeometryNodeInterpolateCurves"_ustr, GEO_NODE_INTERPOLATE_CURVES);
889 ntype.ui_name = "Interpolate Curves";
890 ntype.ui_description = "Generate new curves on points by interpolating between existing curves";
891 ntype.enum_name_legacy = "INTERPOLATE_CURVES";
894 ntype.declare = node_declare;
896}
897NOD_REGISTER_NODE(node_register)
898
899} // namespace blender::nodes::node_geo_interpolate_curves_cc
Low-level operations for curves.
#define NODE_CLASS_GEOMETRY
Definition BKE_node.hh:492
#define GEO_NODE_INTERPOLATE_CURVES
#define NOD_REGISTER_NODE(REGISTER_FUNC)
#define ELEM(...)
void init()
void reinitialize(const int64_t new_size)
Definition BLI_array.hh:430
MutableSpan< T > typed() const
Span< T > typed() const
CommonVArrayInfo common_info() const
constexpr IndexRange index_range() const
Definition BLI_span.hh:676
constexpr Span drop_front(int64_t n) const
Definition BLI_span.hh:175
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
void foreach_attribute(const FunctionRef< void(const AttributeIter &)> fn) const
GAttributeReader get() const
MutableSpan< float3 > positions_for_write()
AttributeAccessor attributes() const
Span< float3 > positions() const
IndexRange curves_range() const
OffsetIndices< int > points_by_curve() const
MutableAttributeAccessor attributes_for_write()
int attribute_domain_size(AttrDomain domain) const
virtual std::optional< AttributeAccessor > attributes() const
virtual bool is_empty() const
bool add(const StringRef name, const AttrDomain domain, const AttrType data_type, const AttributeInit &initializer)
GSpanAttributeWriter lookup_or_add_for_write_only_span(StringRef name, AttrDomain domain, AttrType data_type)
int add(GField field, GVArray *varray_ptr)
const GVArray & get_evaluated(const int field_index) const
static FieldOperationPtr from(std::shared_ptr< const mf::MultiFunction > fn, Vector< GField > inputs)
Definition field.cc:252
NodeAttributeFilter get_attribute_filter(const UString output_identifier) const
std::optional< std::string > get_output_anonymous_attribute_id_if_needed(const UString output_identifier, const bool force_create=false)
T extract_input(const UString identifier)
void set_output(const UString identifier, T &&value)
static void remember_deformed_positions_if_necessary(GeometrySet &geometry)
#define T
void gather(const GVArray &src, const IndexMask &indices, GMutableSpan dst, exec_mode::Mode mode=exec_mode::parallel)
typename DefaultMixerStruct< T >::type DefaultMixer
void to_static_type(const CPPType &cpp_type, Fn &&fn)
void node_register_type(bNodeType &ntype)
Definition node.cc:2920
const MultiFunction & lookup(UString id)
static void find_neighbor_guides(const Span< float3 > positions, const Span< int > point_group_indices, const Span< std::unique_ptr< KDTreeNew< float3 > > > kdtrees, const GroupedSpan< int > guides_by_group, const int max_neighbor_count, MutableSpan< int > r_all_neighbor_indices, MutableSpan< float > r_all_neighbor_weights, MutableSpan< int > r_all_neighbor_counts)
static void parameterize_guide_curves(const bke::CurvesGeometry &guide_curves, Array< int > &r_parameterized_guide_offsets, Array< float > &r_parameterized_guide_lengths)
static void node_declare(NodeDeclarationBuilder &b)
static void compute_point_counts_per_child(const bke::CurvesGeometry &guide_curves, const Span< int > point_group_indices, const Span< int > points_per_curve_by_group, const Span< int > all_neighbor_indices, const Span< float > all_neighbor_weights, const Span< int > all_neighbor_counts, const int max_neighbors, MutableSpan< int > r_points_per_child, MutableSpan< bool > r_use_direct_interpolation)
static Array< std::unique_ptr< KDTreeNew< float3 > > > build_kdtrees_for_root_positions(const GroupedSpan< int > guides_by_group, const Span< float3 > root_positions)
static void interpolate_curve_attributes(bke::CurvesGeometry &child_curves, const bke::CurvesGeometry &guide_curves, const AttributeAccessor &point_attributes, const AttributeFilter &attribute_filter, const int max_neighbors, const Span< int > all_neighbor_indices, const Span< float > all_neighbor_weights, const Span< int > all_neighbor_counts, const OffsetIndices< int > parameterized_guide_offsets, const Span< float > parameterized_guide_lengths, const Span< bool > use_direct_interpolation_per_child)
static void interpolate_curve_shapes(bke::CurvesGeometry &child_curves, const bke::CurvesGeometry &guide_curves, const int max_neighbors, const Span< int > all_neighbor_indices, const Span< float > all_neighbor_weights, const Span< int > all_neighbor_counts, const VArray< float3 > &guides_up, const VArray< float3 > &points_up, const Span< float3 > point_positions, const OffsetIndices< int > parameterized_guide_offsets, const Span< float > parameterized_guide_lengths, const Span< bool > use_direct_interpolation_per_child)
static Array< int > compute_points_per_curve_by_group(const GroupedSpan< int > guides_by_group, const bke::CurvesGeometry &guide_curves)
static void store_output_attributes(bke::CurvesGeometry &child_curves, const std::optional< StringRef > &weight_attribute_id, const std::optional< StringRef > &index_attribute_id, const int max_neighbors, const Span< int > all_neighbor_counts, const Span< int > all_neighbor_indices, const Span< float > all_neighbor_weights)
static GeometrySet generate_interpolated_curves(const Curves &guide_curves_id, const AttributeAccessor &point_attributes, const VArray< float3 > &guides_up, const VArray< float3 > &points_up, const Span< int > guide_group_ids, const VArray< int > &point_group_ids, const int max_neighbors, const AttributeFilter &attribute_filter, const std::optional< StringRef > &index_attribute_id, const std::optional< StringRef > &weight_attribute_id)
OffsetIndices< int > accumulate_counts_to_offsets(MutableSpan< int > counts_to_offsets, int start_offset=0)
GroupedSpan< int > build_groups_from_indices(Span< int > indices, int groups_num, Array< int > &offset_data, Array< int > &index_data)
void parallel_for(const IndexRange range, const int64_t grain_size, const Function &function, const TaskSizeHints &size_hints=detail::TaskSizeHints_Static(1))
Definition BLI_task.hh:69
auto accumulated_task_sizes(Fn &&fn)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
@ CURVE_TYPE_CATMULL_ROM
VecBase< float, 3 > float3
void geo_node_type_base(bke::bNodeType *ntype, UString idname, const std::optional< int16_t > legacy_type)
bool allow_skip(const StringRef name) const
StringRefNull name() const
void set_name(std::string name)
const GeometryComponent * get_component(GeometryComponent::Type component_type) const
const Curves * get_curves() const
void copy_bundle_from(const GeometrySet &other)
void add(const GeometryComponent &component)
Defines a node type.
Definition BKE_node.hh:265
std::string ui_description
Definition BKE_node.hh:271
NodeGeometryExecFunction geometry_node_execute
Definition BKE_node.hh:385
const char * enum_name_legacy
Definition BKE_node.hh:274
NodeDeclareFunction declare
Definition BKE_node.hh:393