Blender V5.3
grease_pencil_geom.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
8
9#include <algorithm>
10
11#include "BLI_array_utils.hh"
13#include "BLI_kdopbvh.hh"
14#include "BLI_kdtree.hh"
15#include "BLI_math_vector.hh"
16#include "BLI_offset_indices.hh"
17#include "BLI_rect.hh"
18#include "BLI_stack.hh"
19#include "BLI_task.hh"
20
21#include "BKE_attribute.hh"
22#include "BKE_curves.hh"
23#include "BKE_curves_utils.hh"
24#include "BKE_deform.hh"
25#include "BKE_grease_pencil.hh"
26
27#include "DNA_curves_types.h"
29
30#include "ED_curves.hh"
31#include "ED_grease_pencil.hh"
32#include "ED_view3d.hh"
33
34#include "GEO_merge_curves.hh"
35
36namespace blender {
37
38extern "C" {
39#include "curve_fit_nd.h"
40}
41
42namespace ed::greasepencil {
43
45 const IndexRange range,
46 const float epsilon,
47 const FunctionRef<float(int64_t, int64_t, int64_t)> dist_function,
48 MutableSpan<bool> points_to_delete)
49{
50 /* Mark all points to not be removed. */
51 points_to_delete.slice(range).fill(false);
52 int64_t total_points_to_remove = 0;
53
55 stack.push(range);
56 while (!stack.is_empty()) {
57 const IndexRange sub_range = stack.pop();
58 /* Skip ranges with less than 3 points. All points are kept. */
59 if (sub_range.size() < 3) {
60 continue;
61 }
62 const IndexRange inside_range = sub_range.drop_front(1).drop_back(1);
63 /* Compute the maximum distance and the corresponding index. */
64 float max_dist = -1.0f;
65 int max_index = -1;
66 for (const int64_t index : inside_range) {
67 const float dist = dist_function(sub_range.first(), sub_range.last(), index);
68 if (dist > max_dist) {
69 max_dist = dist;
70 max_index = index - sub_range.first();
71 }
72 }
73
74 if (max_dist > epsilon) {
75 /* Found point outside the epsilon-sized strip. The point at `max_index` will be kept, repeat
76 * the search on the left & right side. */
77 stack.push(sub_range.slice(0, max_index + 1));
78 stack.push(sub_range.slice(max_index, sub_range.size() - max_index));
79 }
80 else {
81 /* Points in `sub_range` are inside the epsilon-sized strip. Mark them to be deleted. */
82 total_points_to_remove += inside_range.size();
83 points_to_delete.slice(inside_range).fill(true);
84 }
85 }
86 return total_points_to_remove;
87}
88
90 const float error_threshold,
91 const IndexMask &corner_mask)
92{
93 if (points.is_empty()) {
94 return {};
95 }
96 double total_length = 0.0;
97 for (const int point_i : points.index_range().drop_front(1)) {
98 total_length += math::distance(points[point_i - 1], points[point_i]);
99 }
100 /* Just return a dot. */
101 if (total_length < 1e-8) {
102 return Array<float2>({points[0], points[0], points[0]});
103 }
104
105 Array<int32_t> indices(corner_mask.size());
106 corner_mask.to_indices(indices.as_mutable_span());
107 uint *indices_ptr = corner_mask.is_empty() ? nullptr : reinterpret_cast<uint *>(indices.data());
108
109 float *cubic_array;
110 uint cubic_array_len;
111 int error = curve_fit_cubic_to_points_fl(*points.data(),
112 points.size(),
113 2,
114 error_threshold,
115 CURVE_FIT_CALC_HIGH_QUALITY,
116 indices_ptr,
117 indices.size(),
118 &cubic_array,
119 &cubic_array_len,
120 nullptr,
121 nullptr,
122 nullptr);
123
124 if (error != 0) {
125 /* Some error occurred. Return. */
126 return {};
127 }
128
129 if (cubic_array == nullptr) {
130 return {};
131 }
132
133 Span<float2> cubic_array_span(reinterpret_cast<float2 *>(cubic_array), cubic_array_len * 3);
134 Array<float2> curve_positions(cubic_array_span);
135 /* Free the c-style array. */
136 free(cubic_array);
137 return curve_positions;
138}
139
141 const float radius_min,
142 const float radius_max,
143 const int samples_max,
144 const float angle_threshold,
145 IndexMaskMemory &memory)
146{
147 if (points.is_empty()) {
148 return {};
149 }
150 if (points.size() == 1) {
151 return IndexMask::from_indices<int>({0}, memory);
152 }
153 uint *corners;
154 uint corners_len;
155 const int error = curve_fit_corners_detect_fl(*points.data(),
156 points.size(),
158 radius_min,
159 radius_max,
160 samples_max,
161 angle_threshold,
162 &corners,
163 &corners_len);
164 if (error != 0) {
165 /* Error occurred, return. */
166 return IndexMask();
167 }
168
169 if (corners == nullptr) {
170 return IndexMask();
171 }
172
173 BLI_assert(samples_max < std::numeric_limits<int>::max());
174 Span<int> indices(reinterpret_cast<int *>(corners), corners_len);
175 const IndexMask corner_mask = IndexMask::from_indices<int>(indices, memory);
176 /* Free the c-style array. */
177 free(corners);
178 return corner_mask;
179}
180
182 const Span<float> distances,
183 const IndexMask &selection,
184 const float merge_distance,
185 MutableSpan<int> r_merge_indices)
186{
187 /* We use a KDTree<float> here, because we can only merge neighboring points in the curves. */
188 KDTree<float> *tree = kdtree_new<float>(selection.size());
189 /* The selection is an IndexMask of the points just in this curve. */
190 selection.foreach_index([&](const int64_t i, const int64_t pos) {
191 kdtree_insert<float>(tree, pos, distances[i - points.first()]);
192 });
194
195 Array<int> selection_merge_indices(selection.size(), -1);
196 const int duplicate_count = kdtree_calc_duplicates_fast<float>(
197 tree, merge_distance, false, selection_merge_indices.data());
198 kdtree_free<float>(tree);
199
200 array_utils::fill_index_range<int>(r_merge_indices);
201
202 selection.foreach_index([&](const int src_index, const int pos) {
203 const int merge_index = selection_merge_indices[pos];
204 if (merge_index != -1) {
205 const int src_merge_index = selection[merge_index] - points.first();
206 r_merge_indices[src_index - points.first()] = src_merge_index;
207 }
208 });
209
210 return duplicate_count;
211}
212
214 const float merge_distance,
215 const IndexMask &selection,
216 const bke::AttributeFilter &attribute_filter)
217{
218 /* NOTE: The code here is an adapted version of #geometry::point_merge_by_distance. */
219
220 const int src_point_size = src_curves.points_num();
221 if (src_point_size == 0) {
222 return {};
223 }
224 const OffsetIndices<int> points_by_curve = src_curves.points_by_curve();
225 const VArray<bool> cyclic = src_curves.cyclic();
226 src_curves.ensure_evaluated_lengths();
227
229
231
232 MutableSpan<int> dst_offsets = dst_curves.offsets_for_write();
233
234 std::atomic<int> total_duplicate_count = 0;
235 Array<Array<int>> merge_indices_per_curve(src_curves.curves_num());
236 threading::parallel_for(src_curves.curves_range(), 512, [&](const IndexRange range) {
237 for (const int curve_i : range) {
238 const IndexRange points = points_by_curve[curve_i];
239 merge_indices_per_curve[curve_i].reinitialize(points.size());
240
241 Array<float> distances_along_curve(points.size() + int(cyclic[curve_i]));
242 distances_along_curve.first() = 0.0f;
243 const Span<float> lengths = src_curves.evaluated_lengths_for_curve(curve_i, cyclic[curve_i]);
244 distances_along_curve.as_mutable_span().drop_front(1).copy_from(lengths);
245
246 MutableSpan<int> merge_indices = merge_indices_per_curve[curve_i].as_mutable_span();
247 array_utils::fill_index_range<int>(merge_indices);
248
249 const int duplicate_count = curve_merge_by_distance(points,
250 distances_along_curve,
251 selection.slice_content(points),
252 merge_distance,
253 merge_indices);
254 /* Write the curve size. The counts will be accumulated to offsets below. */
255 dst_offsets[curve_i] = points.size() - duplicate_count;
256 total_duplicate_count += duplicate_count;
257 }
258 });
259
260 const int dst_point_size = src_point_size - total_duplicate_count;
261 dst_curves.resize(dst_point_size, src_curves.curves_num());
263
264 int merged_points = 0;
265 Array<int> src_to_dst_indices(src_point_size);
266 for (const int curve_i : src_curves.curves_range()) {
267 const IndexRange points = points_by_curve[curve_i];
268 const Span<int> merge_indices = merge_indices_per_curve[curve_i].as_span();
269 for (const int i : points.index_range()) {
270 const int point_i = points.start() + i;
271 src_to_dst_indices[point_i] = point_i - merged_points;
272 if (merge_indices[i] != i) {
273 merged_points++;
274 }
275 }
276 }
277
278 Array<int> point_merge_counts(dst_point_size, 0);
279 for (const int curve_i : src_curves.curves_range()) {
280 const IndexRange points = points_by_curve[curve_i];
281 const Span<int> merge_indices = merge_indices_per_curve[curve_i].as_span();
282 for (const int i : points.index_range()) {
283 const int merge_index = merge_indices[i];
284 const int point_src = points.start() + merge_index;
285 const int dst_index = src_to_dst_indices[point_src];
286 point_merge_counts[dst_index]++;
287 }
288 }
289
290 Array<int> map_offsets_data(dst_point_size + 1);
291 map_offsets_data.as_mutable_span().drop_back(1).copy_from(point_merge_counts);
292 OffsetIndices<int> map_offsets = offset_indices::accumulate_counts_to_offsets(map_offsets_data);
293
294 point_merge_counts.fill(0);
295
296 Array<int> merge_map_indices(src_point_size);
297 for (const int curve_i : src_curves.curves_range()) {
298 const IndexRange points = points_by_curve[curve_i];
299 const Span<int> merge_indices = merge_indices_per_curve[curve_i].as_span();
300 for (const int i : points.index_range()) {
301 const int point_i = points.start() + i;
302 const int merge_index = merge_indices[i];
303 const int dst_index = src_to_dst_indices[points.start() + merge_index];
304 merge_map_indices[map_offsets[dst_index].first() + point_merge_counts[dst_index]] = point_i;
305 point_merge_counts[dst_index]++;
306 }
307 }
308
309 bke::AttributeAccessor src_attributes = src_curves.attributes();
310 bke::MutableAttributeAccessor dst_attributes = dst_curves.attributes_for_write();
311 src_attributes.foreach_attribute([&](const bke::AttributeIter &iter) {
312 if (attribute_filter.allow_skip(iter.name)) {
313 return;
314 }
315 if (iter.domain != bke::AttrDomain::Point) {
316 return;
317 }
318 bke::GAttributeReader src_attribute = iter.get();
319 const CommonVArrayInfo info = src_attribute.varray.common_info();
320 if (info.type == CommonVArrayInfo::Type::Single) {
321 const bke::AttributeInitValue init(GPointer(src_attribute.varray.type(), info.data));
322 if (dst_attributes.add(iter.name, iter.domain, iter.data_type, init)) {
323 return;
324 }
325 }
326
327 bke::GSpanAttributeWriter dst_attribute = dst_attributes.lookup_or_add_for_write_only_span(
328 iter.name, bke::AttrDomain::Point, iter.data_type);
329 bke::attribute_math::mix_groups(GVArraySpan(src_attribute.varray),
330 map_offsets,
331 merge_map_indices,
332 std::nullopt,
333 dst_attribute.span);
334 dst_attribute.finish();
335 });
336
337 if (dst_curves.nurbs_has_custom_knots()) {
339 dst_curves.curves_range(), NURBS_KNOT_MODE_NORMAL, NURBS_KNOT_MODE_NORMAL, dst_curves);
340 }
341 return dst_curves;
342}
343
345 const ARegion &region,
346 const bke::CurvesGeometry &src_curves,
347 const float4x4 &layer_to_world,
348 const float merge_distance,
349 const IndexMask &selection,
350 const bke::AttributeFilter &attribute_filter)
351{
352 const OffsetIndices src_points_by_curve = src_curves.points_by_curve();
353 const Span<float3> src_positions = src_curves.positions();
354 const float merge_distance_squared = merge_distance * merge_distance;
355
356 Array<float2> screen_start_points(src_curves.curves_num());
357 Array<float2> screen_end_points(src_curves.curves_num());
358 const VArray<bool> cyclic = *src_curves.attributes().lookup_or_default<bool>(
359 "cyclic", bke::AttrDomain::Curve, false);
360 /* For comparing screen space positions use a 2D KDTree. Each curve adds 2 points. */
361 KDTree<float2> *tree = kdtree_new<float2>(2 * src_curves.curves_num());
362
363 threading::parallel_for(src_curves.curves_range(), 1024, [&](const IndexRange range) {
364 for (const int src_i : range) {
365 const IndexRange points = src_points_by_curve[src_i];
366 const float3 start_pos = src_positions[points.first()];
367 const float3 end_pos = src_positions[points.last()];
368 const float3 start_world = math::transform_point(layer_to_world, start_pos);
369 const float3 end_world = math::transform_point(layer_to_world, end_pos);
370
371 ED_view3d_project_float_global(
372 &region, start_world, screen_start_points[src_i], V3D_PROJ_TEST_NOP);
373 ED_view3d_project_float_global(
374 &region, end_world, screen_end_points[src_i], V3D_PROJ_TEST_NOP);
375 }
376 });
377 /* Note: KDTree insertion is not thread-safe, don't parallelize this. */
378 for (const int src_i : src_curves.curves_range()) {
379 if (cyclic[src_i] == true) {
380 continue;
381 }
382 kdtree_insert<float2>(tree, src_i * 2, screen_start_points[src_i]);
383 kdtree_insert<float2>(tree, src_i * 2 + 1, screen_end_points[src_i]);
384 }
386
387 Array<int> connect_to_curve(src_curves.curves_num(), -1);
388 Array<bool> flip_direction(src_curves.curves_num(), false);
389 selection.foreach_index(
390 [&](const int src_i) {
391 const float2 &start_co = screen_start_points[src_i];
392 const float2 &end_co = screen_end_points[src_i];
393 /* Index of KDTree points so they can be ignored. */
394 const int start_index = src_i * 2;
395 const int end_index = src_i * 2 + 1;
396
397 KDTreeNearest<float2> nearest_start, nearest_end;
398 const bool is_start_ok =
400 tree,
401 start_co,
402 &nearest_start,
403 [&](const int other, const float2 & /*co*/, const float dist_sq) {
404 if (start_index == other || dist_sq > merge_distance_squared) {
405 return 0;
406 }
407 return 1;
408 }) != -1);
409 const bool is_end_ok =
411 tree,
412 end_co,
413 &nearest_end,
414 [&](const int other, const float2 & /*co*/, const float dist_sq) {
415 if (end_index == other || dist_sq > merge_distance_squared) {
416 return 0;
417 }
418 return 1;
419 }) != -1);
420
421 if (is_start_ok) {
422 const int curve_index = nearest_start.index / 2;
423 const bool is_end_point = bool(nearest_start.index % 2);
424 if (connect_to_curve[curve_index] < 0) {
425 connect_to_curve[curve_index] = src_i;
426 flip_direction[curve_index] = !is_end_point;
427 }
428 }
429 if (is_end_ok) {
430 const int curve_index = nearest_end.index / 2;
431 const bool is_end_point = bool(nearest_end.index % 2);
432 if (connect_to_curve[src_i] < 0) {
433 connect_to_curve[src_i] = curve_index;
434 flip_direction[curve_index] = is_end_point;
435 }
436 }
437 },
440
442 src_curves, connect_to_curve, flip_direction, attribute_filter);
443}
444
445/* Generate a full circle around a point. */
446static void generate_circle_from_point(const float3 &pt,
447 const float radius,
448 const int corner_subdivisions,
449 const int src_point_index,
450 Vector<float3> &r_perimeter,
451 Vector<int> &r_src_indices)
452{
453 /* Number of points is 2^(n+2) on a full circle (n=corner_subdivisions). */
454 BLI_assert(corner_subdivisions >= 0);
455 const int num_points = 1 << (corner_subdivisions + 2);
456 const float delta_angle = 2 * M_PI / float(num_points);
457 const float delta_cos = math::cos(delta_angle);
458 const float delta_sin = math::sin(delta_angle);
459
460 float3 vec = float3(radius, 0, 0);
461 for ([[maybe_unused]] const int i : IndexRange(num_points)) {
462 r_perimeter.append(pt + vec);
463 r_src_indices.append(src_point_index);
464
465 const float x = delta_cos * vec.x - delta_sin * vec.y;
466 const float y = delta_sin * vec.x + delta_cos * vec.y;
467 vec = float3(x, y, 0.0f);
468 }
469}
470
471/* Generate points in an counter-clockwise arc between two directions. */
473 const float3 &to,
474 const float3 &center_pt,
475 const int corner_subdivisions,
476 const int src_point_index,
477 Vector<float3> &r_perimeter,
478 Vector<int> &r_src_indices)
479{
480 const float3 vec_from = from - center_pt;
481 const float3 vec_to = to - center_pt;
482 if (math::is_zero(vec_from) || math::is_zero(vec_to)) {
483 r_perimeter.append(center_pt);
484 r_src_indices.append(src_point_index);
485 return;
486 }
487
488 const float cos_angle = math::dot(vec_from.xy(), vec_to.xy());
489 const float sin_angle = vec_from.x * vec_to.y - vec_from.y * vec_to.x;
490 /* Compute angle in range [0, 2pi) so that the rotation is always counter-clockwise. */
491 const float angle = math::atan2(-sin_angle, -cos_angle) + M_PI;
492
493 /* Number of points is 2^(n+1) + 1 on half a circle (n=corner_subdivisions)
494 * so we multiply by (angle / pi) to get the right amount of
495 * points to insert. */
496 const int num_full = (1 << (corner_subdivisions + 1)) + 1;
497 const int num_points = num_full * math::abs(angle) / M_PI;
498 if (num_points < 2) {
499 r_perimeter.append(center_pt + vec_from);
500 r_src_indices.append(src_point_index);
501 return;
502 }
503 const float delta_angle = angle / float(num_points - 1);
504 const float delta_cos = math::cos(delta_angle);
505 const float delta_sin = math::sin(delta_angle);
506
507 float3 vec = vec_from;
508 for ([[maybe_unused]] const int i : IndexRange(num_points)) {
509 r_perimeter.append(center_pt + vec);
510 r_src_indices.append(src_point_index);
511
512 const float x = delta_cos * vec.x - delta_sin * vec.y;
513 const float y = delta_sin * vec.x + delta_cos * vec.y;
514 vec = float3(x, y, 0.0f);
515 }
516}
517
518/* Generate a semi-circle around a point, opposite the direction. */
519static void generate_cap(const float3 &point,
520 const float3 &tangent,
521 const float radius,
522 const int corner_subdivisions,
523 const eGPDstroke_Caps cap_type,
524 const int src_point_index,
525 Vector<float3> &r_perimeter,
526 Vector<int> &r_src_indices)
527{
528 const float3 normal = math::normalize(float3{tangent.y, -tangent.x, 0.0f});
529 switch (cap_type) {
531 generate_arc_from_point_to_point(point - normal * radius,
532 point + normal * radius,
533 point,
534 corner_subdivisions,
535 src_point_index,
536 r_perimeter,
537 r_src_indices);
538 break;
540 r_perimeter.append(point - normal * radius);
541 r_src_indices.append(src_point_index);
542 r_perimeter.append(point + normal * radius);
543 r_src_indices.append(src_point_index);
544 break;
547 break;
548 }
549}
550
551/* Generate a corner between two segments, using `miter_limit_angle` as the corner type.
552 * NOTE: The perimeter is considered to be to the right hand side of the stroke. The left side
553 * perimeter can be generated by reversing the order of points. */
554static void generate_corner(const float3 &pt_a,
555 const float3 &pt_b,
556 const float3 &pt_c,
557 const float radius,
558 const float miter_limit_angle,
559 const int corner_subdivisions,
560 const int src_point_index,
561 Vector<float3> &r_perimeter,
562 Vector<int> &r_src_indices)
563{
564 const float length = math::length(pt_c - pt_b);
565 const float length_prev = math::length(pt_b - pt_a);
566 const float2 tangent = math::normalize((pt_c - pt_b).xy());
567 const float2 tangent_prev = math::normalize((pt_b - pt_a).xy());
568 const float3 normal = {tangent.y, -tangent.x, 0.0f};
569 const float3 normal_prev = {tangent_prev.y, -tangent_prev.x, 0.0f};
570
571 const float sin_angle = tangent_prev.x * tangent.y - tangent_prev.y * tangent.x;
572 /* Whether the corner is an inside or outside corner.
573 * This determines whether an arc is added or a single miter point. */
574 const bool is_outside_corner = (sin_angle >= 0.0f);
575 if (is_outside_corner && miter_limit_angle <= GP_STROKE_MITER_ANGLE_ROUND) {
576 generate_arc_from_point_to_point(pt_b + normal_prev * radius,
577 pt_b + normal * radius,
578 pt_b,
579 corner_subdivisions,
580 src_point_index,
581 r_perimeter,
582 r_src_indices);
583 return;
584 }
585
586 const float2 avg_tangent = math::normalize(tangent_prev + tangent);
587 const float3 miter = {avg_tangent.y, -avg_tangent.x, 0.0f};
588 const float miter_invscale = math::dot(normal, miter);
589
590 if (is_outside_corner) {
591 const bool is_bevel = -math::dot(tangent, tangent_prev) > math::cos(miter_limit_angle);
592 if (is_bevel) {
593 r_perimeter.append(pt_b + normal_prev * radius);
594 r_perimeter.append(pt_b + normal * radius);
595 r_src_indices.append_n_times(src_point_index, 2);
596 return;
597 }
598 const float3 miter_point = pt_b + miter * radius / miter_invscale;
599 r_perimeter.append(miter_point);
600 r_src_indices.append(src_point_index);
601 return;
602 }
603
604 /* Avoid division by tiny values for steep angles. */
605 const float3 miter_point = (radius < length * miter_invscale &&
606 radius < length_prev * miter_invscale) ?
607 pt_b + miter * radius / miter_invscale :
608 pt_b + miter * radius;
609
610 r_perimeter.append(miter_point);
611 r_src_indices.append(src_point_index);
612}
613
614static void generate_stroke_perimeter(const Span<float3> all_positions,
615 const Span<float> all_radii,
616 const IndexRange points,
617 const int corner_subdivisions,
618 const bool is_cyclic,
619 const bool use_caps,
620 const eGPDstroke_Caps start_cap_type,
621 const eGPDstroke_Caps end_cap_type,
622 const VArray<float> miter_angles,
623 const float outline_offset,
624 Vector<float3> &r_perimeter,
625 Vector<int> &r_point_counts,
626 Vector<int> &r_point_indices)
627{
628 const Span<float3> positions = all_positions.slice(points);
629 const int point_num = points.size();
630 if (point_num == 0) {
631 return;
632 }
633 if (point_num == 1) {
634 /* Generate a circle for a single point. */
635 const int perimeter_start = r_perimeter.size();
636 const int point = points.first();
637 const float radius = std::max(all_radii[point] + outline_offset, 0.0f);
639 positions.first(), radius, corner_subdivisions, point, r_perimeter, r_point_indices);
640 const int perimeter_count = r_perimeter.size() - perimeter_start;
641 if (perimeter_count > 0) {
642 r_point_counts.append(perimeter_count);
643 }
644 return;
645 }
646
647 auto add_corner = [&](const int a, const int b, const int c) {
648 const int point = points[b];
649 const float3 pt_a = positions[a];
650 const float3 pt_b = positions[b];
651 const float3 pt_c = positions[c];
652 const float radius = std::max(all_radii[point] + outline_offset, 0.0f);
653 const float miter_angle = miter_angles[point];
654 generate_corner(pt_a,
655 pt_b,
656 pt_c,
657 radius,
658 miter_angle,
659 corner_subdivisions,
660 point,
661 r_perimeter,
662 r_point_indices);
663 };
664 auto add_cap = [&](const int center_i, const int next_i, const eGPDstroke_Caps cap_type) {
665 const int point = points[center_i];
666 const float3 &center = positions[center_i];
667 const float3 dir = math::normalize(positions[next_i] - center);
668 const float radius = std::max(all_radii[point] + outline_offset, 0.0f);
670 center, dir, radius, corner_subdivisions, cap_type, point, r_perimeter, r_point_indices);
671 };
672
673 /* Creates a single cyclic curve with end caps. */
674 if (use_caps) {
675 /* Open curves generate a start and end cap and a connecting stroke on either side. */
676 const int perimeter_start = r_perimeter.size();
677
678 /* Start cap. */
679 add_cap(0, 1, start_cap_type);
680
681 /* Right perimeter half. */
682 for (const int i : points.index_range().drop_front(1).drop_back(1)) {
683 add_corner(i - 1, i, i + 1);
684 }
685 if (is_cyclic) {
686 add_corner(point_num - 2, point_num - 1, 0);
687 }
688
689 /* End cap. */
690 if (is_cyclic) {
691 /* End point is same as start point. */
692 add_cap(0, point_num - 1, end_cap_type);
693 }
694 else {
695 /* End point is last point of the curve. */
696 add_cap(point_num - 1, point_num - 2, end_cap_type);
697 }
698
699 /* Left perimeter half. */
700 if (is_cyclic) {
701 add_corner(0, point_num - 1, point_num - 2);
702 }
703 for (const int i : points.index_range().drop_front(1).drop_back(1)) {
704 add_corner(point_num - i, point_num - i - 1, point_num - i - 2);
705 }
706
707 const int perimeter_count = r_perimeter.size() - perimeter_start;
708 if (perimeter_count > 0) {
709 r_point_counts.append(perimeter_count);
710 }
711 }
712 else {
713 /* Generate separate "inside" and an "outside" perimeter curves.
714 * The distinction is arbitrary, called left/right here. */
715
716 /* Right side perimeter. */
717 const int left_perimeter_start = r_perimeter.size();
718 add_corner(point_num - 1, 0, 1);
719 for (const int i : points.index_range().drop_front(1).drop_back(1)) {
720 add_corner(i - 1, i, i + 1);
721 }
722 add_corner(point_num - 2, point_num - 1, 0);
723 const int left_perimeter_count = r_perimeter.size() - left_perimeter_start;
724 if (left_perimeter_count > 0) {
725 r_point_counts.append(left_perimeter_count);
726 }
727
728 /* Left side perimeter. */
729 const int right_perimeter_start = r_perimeter.size();
730 add_corner(0, point_num - 1, point_num - 2);
731 for (const int i : points.index_range().drop_front(1).drop_back(1)) {
732 add_corner(point_num - i, point_num - i - 1, point_num - i - 2);
733 }
734 add_corner(1, 0, point_num - 1);
735 const int right_perimeter_count = r_perimeter.size() - right_perimeter_start;
736 if (right_perimeter_count > 0) {
737 r_point_counts.append(right_perimeter_count);
738 }
739 }
740}
741
743 /* New points per curve count. */
745 /* New point coordinates. */
747 /* Source curve index. */
749 /* Source point index. */
751};
752
754 const IndexMask &strokes,
755 const float4x4 &transform,
756 const int corner_subdivisions,
757 const float outline_radius,
758 const float outline_offset,
759 const int material_index)
760{
761 const bke::CurvesGeometry &src_curves = drawing.strokes();
762 Span<float3> src_positions = src_curves.positions();
763 bke::AttributeAccessor src_attributes = src_curves.attributes();
764 const VArray<float> src_radii = drawing.radii();
765 const VArray<bool> src_cyclic = *src_attributes.lookup_or_default(
766 "cyclic", bke::AttrDomain::Curve, false);
767 const VArray<int8_t> src_start_caps = *src_attributes.lookup_or_default<int8_t>(
769 const VArray<int8_t> src_end_caps = *src_attributes.lookup_or_default<int8_t>(
771 const VArray<int> src_material_index = *src_attributes.lookup_or_default(
772 "material_index", bke::AttrDomain::Curve, 0);
773 const VArray<float> miter_angles = *src_attributes.lookup_or_default<float>(
775 const VArray<int> src_fill_ids = *src_attributes.lookup_or_default(
776 "fill_id", bke::AttrDomain::Curve, 0);
777
778 /* Transform positions and radii. */
779 Array<float3> transformed_positions(src_positions.size());
780 math::transform_points(src_positions, transform, transformed_positions);
781
782 Array<float> transformed_radii(src_radii.size());
784 threading::parallel_for(transformed_radii.index_range(), 4096, [&](const IndexRange range) {
785 for (const int i : range) {
786 transformed_radii[i] = src_radii[i] * scale;
787 }
788 });
789
790 const float4x4 transform_inv = math::invert(transform);
792 strokes.foreach_index(
793 [&](const int64_t curve_i) {
794 PerimeterData &data = thread_data.local();
795
796 const bool is_cyclic_curve = src_cyclic[curve_i];
797 const bool use_caps = !is_cyclic_curve;
798
799 const int prev_point_num = data.positions.size();
800 const int prev_curve_num = data.point_counts.size();
801 const IndexRange points = src_curves.points_by_curve()[curve_i];
802
803 generate_stroke_perimeter(transformed_positions,
804 transformed_radii,
805 points,
806 corner_subdivisions,
807 is_cyclic_curve,
808 use_caps,
809 eGPDstroke_Caps(src_start_caps[curve_i]),
810 eGPDstroke_Caps(src_end_caps[curve_i]),
811 miter_angles,
812 outline_offset,
813 data.positions,
814 data.point_counts,
815 data.point_indices);
816
817 /* Transform perimeter positions back into object space. */
818 math::transform_points(transform_inv,
819 data.positions.as_mutable_span().drop_front(prev_point_num));
820
821 data.curve_indices.append_n_times(curve_i, data.point_counts.size() - prev_curve_num);
822 },
824
825 int dst_curve_num = 0;
826 int dst_point_num = 0;
827 for (const PerimeterData &data : thread_data) {
828 BLI_assert(data.point_counts.size() == data.curve_indices.size());
829 BLI_assert(data.positions.size() == data.point_indices.size());
830 dst_curve_num += data.point_counts.size();
831 dst_point_num += data.positions.size();
832 }
833
834 bke::CurvesGeometry dst_curves(dst_point_num, dst_curve_num);
835 if (dst_point_num == 0 || dst_curve_num == 0) {
836 return dst_curves;
837 }
838
839 bke::MutableAttributeAccessor dst_attributes = dst_curves.attributes_for_write();
840 bke::SpanAttributeWriter<bool> dst_cyclic = dst_attributes.lookup_or_add_for_write_span<bool>(
841 "cyclic", bke::AttrDomain::Curve);
842 bke::SpanAttributeWriter<int> dst_material = dst_attributes.lookup_or_add_for_write_span<int>(
843 "material_index", bke::AttrDomain::Curve);
844 bke::SpanAttributeWriter<float> dst_radius = dst_attributes.lookup_or_add_for_write_span<float>(
845 "radius", bke::AttrDomain::Point);
846 bke::SpanAttributeWriter<int> dst_fill_ids = dst_attributes.lookup_or_add_for_write_span<int>(
847 "fill_id", bke::AttrDomain::Curve);
848 const MutableSpan<int> dst_offsets = dst_curves.offsets_for_write();
849 const MutableSpan<float3> dst_positions = dst_curves.positions_for_write();
850 /* Source indices for attribute mapping. */
851 Array<int> dst_curve_map(dst_curve_num);
852 Array<int> dst_point_map(dst_point_num);
853
854 /* Start at `1` for the new geometry. */
855 int fill_id_to_set = 1;
856 Map<int, int> fill_src_id_to_dst_id;
857
858 IndexRange curves;
859 IndexRange points;
860 for (const PerimeterData &data : thread_data) {
861 curves = curves.after(data.point_counts.size());
862 points = points.after(data.positions.size());
863
864 /* Append curve data. */
865 dst_curve_map.as_mutable_span().slice(curves).copy_from(data.curve_indices);
866 /* Curve offsets are accumulated below. */
867 dst_offsets.slice(curves).copy_from(data.point_counts);
868 dst_cyclic.span.slice(curves).fill(true);
869 if (material_index >= 0) {
870 dst_material.span.slice(curves).fill(material_index);
871 }
872 else {
873 for (const int i : curves.index_range()) {
874 dst_material.span[curves[i]] = src_material_index[data.curve_indices[i]];
875 }
876 }
877
878 for (const int i : curves.index_range()) {
879 const int dst_curve_i = curves[i];
880 const int src_curve_i = data.curve_indices[i];
881 const int src_fill_id = src_fill_ids[src_curve_i];
882
883 if (src_fill_id == 0) {
884 dst_fill_ids.span[dst_curve_i] = fill_id_to_set;
885 fill_id_to_set++;
886 }
887 else {
888 if (const std::optional<int> dst_fill_id = fill_src_id_to_dst_id.lookup_try(src_fill_id)) {
889 dst_fill_ids.span[dst_curve_i] = *dst_fill_id;
890 }
891 else {
892 dst_fill_ids.span[dst_curve_i] = fill_id_to_set;
893 fill_src_id_to_dst_id.add(src_fill_id, fill_id_to_set);
894 fill_id_to_set++;
895 }
896 }
897 }
898
899 /* Append point data. */
900 dst_positions.slice(points).copy_from(data.positions);
901 dst_point_map.as_mutable_span().slice(points).copy_from(data.point_indices);
902 dst_radius.span.slice(points).fill(outline_radius);
903 }
904 offset_indices::accumulate_counts_to_offsets(dst_curves.offsets_for_write());
905
906 bke::gather_attributes(src_attributes,
907 bke::AttrDomain::Point,
908 bke::AttrDomain::Point,
909 bke::attribute_filter_from_skip_ref({"position", "radius"}),
910 dst_point_map,
911 dst_attributes);
912 bke::gather_attributes(
913 src_attributes,
914 bke::AttrDomain::Curve,
915 bke::AttrDomain::Curve,
916 bke::attribute_filter_from_skip_ref({"cyclic", "material_index", "fill_id"}),
917 dst_curve_map,
918 dst_attributes);
919
920 dst_cyclic.finish();
921 dst_material.finish();
922 dst_radius.finish();
923 dst_fill_ids.finish();
924 dst_curves.update_curve_types();
925
926 return dst_curves;
927}
928
930 const Object &object,
933 const int frame_number)
934{
936
937 /* Upper bound for line count. Arrays are sized for easy index mapping, exact count isn't
938 * necessary. Not all points are added to the BVH tree. */
939 int max_bvh_lines = 0;
940 for (const int i_drawing : drawings.index_range()) {
941 if (drawings[i_drawing].frame_number == frame_number) {
942 max_bvh_lines += drawings[i_drawing].drawing.strokes().evaluated_points_num();
943 }
944 }
945
946 data.tree = BLI_bvhtree_new(max_bvh_lines, 0.0f, 4, 6);
947 data.start_positions.reinitialize(max_bvh_lines);
948 data.end_positions.reinitialize(max_bvh_lines);
949 /* Compute offsets array in advance. */
950 data.drawing_offsets.reinitialize(drawings.size() + 1);
951 for (const int i_drawing : drawings.index_range()) {
952 const MutableDrawingInfo &info = drawings[i_drawing];
953 data.drawing_offsets[i_drawing] = (drawings[i_drawing].frame_number == frame_number ?
954 info.drawing.strokes().evaluated_points_num() :
955 0);
956 }
958 data.drawing_offsets);
959
960 /* Insert a line for each point except end points. */
961 for (const int i_drawing : drawings.index_range()) {
962 const MutableDrawingInfo &info = drawings[i_drawing];
963 if (drawings[i_drawing].frame_number != frame_number) {
964 continue;
965 }
966
968 const float4x4 layer_to_world = layer.to_world_space(object);
969 const float4x4 projection = ED_view3d_ob_project_mat_get_from_obmat(vc.rv3d, layer_to_world);
971 const OffsetIndices evaluated_points_by_curve = curves.evaluated_points_by_curve();
972 const VArray<bool> cyclic = curves.cyclic();
973 const Span<float3> evaluated_positions = curves.evaluated_positions();
974 const IndexMask curves_mask = curves.curves_range();
975
976 /* Range of indices in the BVH tree for this drawing. */
977 const IndexRange bvh_index_range = bvh_elements_by_drawing[i_drawing];
978 const MutableSpan<float2> start_positions = data.start_positions.as_mutable_span().slice(
979 bvh_index_range);
980 const MutableSpan<float2> end_positions = data.end_positions.as_mutable_span().slice(
981 bvh_index_range);
982
983 curves_mask.foreach_index([&](const int i_curve) {
984 const bool is_cyclic = cyclic[i_curve];
985 const IndexRange evaluated_points = evaluated_points_by_curve[i_curve];
986
987 /* Compute screen space positions. */
988 for (const int i_point : evaluated_points) {
990 vc.region, evaluated_positions[i_point], projection);
991 start_positions[i_point] = co;
992
993 /* Last point is only valid for cyclic curves, gets ignored for non-cyclic curves. */
994 const int i_prev_point = (i_point > 0 ? i_point - 1 : evaluated_points.last());
995 end_positions[i_prev_point] = co;
996 }
997
998 for (const int i_point : evaluated_points.drop_back(1)) {
999 const float2 &start = start_positions[i_point];
1000 const float2 &end = end_positions[i_point];
1001
1002 const float bb[6] = {start.x, start.y, 0.0f, end.x, end.y, 0.0f};
1003 BLI_bvhtree_insert(data.tree, bvh_index_range[i_point], bb, 2);
1004 }
1005 /* Last->first point segment only used for cyclic curves. */
1006 if (is_cyclic) {
1007 const float2 &start = start_positions.last();
1008 const float2 &end = end_positions.first();
1009
1010 const float bb[6] = {start.x, start.y, 0.0f, end.x, end.y, 0.0f};
1011 BLI_bvhtree_insert(data.tree, bvh_index_range[evaluated_points.last()], bb, 2);
1012 }
1013 });
1014 }
1015
1017
1018 return data;
1019}
1020
1022{
1023 if (data.tree) {
1024 BLI_bvhtree_free(data.tree);
1025 data.tree = nullptr;
1026 }
1027 data.drawing_offsets.reinitialize(0);
1028 data.start_positions.reinitialize(0);
1029 data.end_positions.reinitialize(0);
1030}
1031
1033 const IndexMask &curve_mask,
1034 const Span<float2> screen_space_positions,
1035 const Curves2DBVHTree &tree_data,
1036 const IndexRange tree_data_range,
1037 MutableSpan<bool> r_hits,
1038 std::optional<MutableSpan<float>> r_first_intersect_factors,
1039 std::optional<MutableSpan<float>> r_last_intersect_factors)
1040{
1041 /* Insert segments for cutting extensions on stroke intersection. */
1042 const OffsetIndices points_by_curve = curves.points_by_curve();
1043 const VArray<bool> cyclic = curves.cyclic();
1044
1045 struct RaycastArgs {
1046 const Curves2DBVHTree &tree_data;
1047 /* Indices that need to be ignored to avoid intersecting a line with itself or its immediate
1048 * neighbors. */
1049 int ignore_index1;
1050 int ignore_index2;
1051 int ignore_index3;
1052 };
1053 BVHTree_RayCastCallback callback =
1054 [](void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit) {
1055 using Result = math::isect_result<float2>;
1056
1057 const RaycastArgs &args = *static_cast<const RaycastArgs *>(userdata);
1058 if (ELEM(index, args.ignore_index1, args.ignore_index2, args.ignore_index3)) {
1059 return;
1060 }
1061
1062 const float2 ray_start = float2(ray->origin);
1063 const float2 ray_end = ray_start + float2(ray->direction) * ray->radius;
1064 const float2 &line_start = args.tree_data.start_positions[index];
1065 const float2 &line_end = args.tree_data.end_positions[index];
1066 Result result = math::isect_seg_seg(ray_start, ray_end, line_start, line_end);
1067 if (result.kind <= 0) {
1068 return;
1069 }
1070 const float dist = result.lambda * math::distance(ray_start, ray_end);
1071 if (dist >= hit->dist) {
1072 return;
1073 }
1074 /* These always need to be calculated for the BVH traversal function. */
1075 hit->index = index;
1076 hit->dist = result.lambda * math::distance(ray_start, ray_end);
1077 /* Don't need the hit point, only the lambda. */
1078 hit->no[0] = result.lambda;
1079 };
1080
1081 /* Ray-cast in the forward direction. Ignores intersections with neighboring lines. */
1082 auto do_raycast = [&](const int index_back,
1083 const int index,
1084 const int index_forward,
1085 float &r_lambda) -> bool {
1086 if (index_forward < 0) {
1087 return false;
1088 }
1089
1090 const float2 start = screen_space_positions[index];
1091 const float2 end = screen_space_positions[index_forward];
1092 float length;
1093 const float2 dir = math::normalize_and_get_length(end - start, length);
1094
1095 RaycastArgs args = {tree_data,
1096 index_back >= 0 ? int(tree_data_range[index_back]) : -1,
1097 int(tree_data_range[index]),
1098 index_forward >= 0 ? int(tree_data_range[index_forward]) : -1};
1099 BVHTreeRayHit hit;
1100 hit.index = -1;
1101 hit.dist = FLT_MAX;
1103 tree_data.tree, float3(start, 0.0f), float3(dir, 0.0f), length, &hit, callback, &args);
1104
1105 if (hit.index >= 0) {
1106 r_lambda = hit.no[0];
1107 return true;
1108 }
1109 return false;
1110 };
1111
1112 r_hits.fill(false);
1113 if (r_first_intersect_factors) {
1114 r_first_intersect_factors->fill(-1.0f);
1115 }
1116 if (r_last_intersect_factors) {
1117 r_last_intersect_factors->fill(-1.0f);
1118 }
1119
1120 curve_mask.foreach_index(
1121 [&](const int i_curve) {
1122 const bool is_cyclic = cyclic[i_curve];
1123 const IndexRange points = points_by_curve[i_curve];
1124
1125 for (const int i_point : points) {
1126 const int i_prev_point = (i_point == points.first() ? (is_cyclic ? points.last() : -1) :
1127 i_point - 1);
1128 const int i_next_point = (i_point == points.last() ? (is_cyclic ? points.first() : -1) :
1129 i_point + 1);
1130 float lambda;
1131 /* Find first intersections by raycast from each point to the next. */
1132 if (do_raycast(i_prev_point, i_point, i_next_point, lambda)) {
1133 r_hits[i_point] = true;
1134 if (r_first_intersect_factors) {
1135 (*r_first_intersect_factors)[i_point] = lambda;
1136 }
1137 }
1138 /* Find last intersections by raycast from each point to the previous. */
1139 if (do_raycast(i_next_point, i_point, i_prev_point, lambda)) {
1140 /* Note: factor = (1 - lambda) because of reverse raycast. */
1141 if (r_last_intersect_factors) {
1142 (*r_last_intersect_factors)[i_point] = 1.0f - lambda;
1143 }
1144 }
1145 }
1146 },
1147 exec_mode::grain_size(1024));
1148}
1149
1151 const IndexMask &curve_mask,
1152 const Span<float2> screen_space_positions,
1153 const Curves2DBVHTree &tree_data,
1154 const IndexRange tree_data_range)
1155{
1156 const OffsetIndices points_by_curve = curves.points_by_curve();
1157 const VArray<bool> cyclic = curves.cyclic();
1158
1159 Array<bool> hits(curves.points_num());
1160 Array<float> first_hit_factors(curves.points_num());
1161 Array<float> last_hit_factors(curves.points_num());
1163 curve_mask,
1164 screen_space_positions,
1165 tree_data,
1166 tree_data_range,
1167 hits,
1168 first_hit_factors,
1169 last_hit_factors);
1170
1171 IndexMaskMemory memory;
1172 const IndexMask hit_mask = IndexMask::from_bools(hits, memory);
1173
1174 /* Count number of segments in each curve.
1175 * This is needed to write to the correct segments range for each curve. */
1177 result.segment_offsets.reinitialize(curves.curves_num() + 1);
1178 /* Only segments with hits are written to, initialize all to zero. */
1179 result.segment_offsets.fill(0);
1180 curve_mask.foreach_index(
1181 [&](const int curve_i) {
1182 const IndexRange points = points_by_curve[curve_i];
1183 const IndexMask curve_hit_mask = hit_mask.slice_content(points);
1184 const bool is_cyclic = cyclic[curve_i];
1185
1186 /* Each hit splits a segment in two. Non-cyclic curves add the curve start point as a
1187 * segment start point. */
1188 result.segment_offsets[curve_i] = (is_cyclic ? 0 : 1) + curve_hit_mask.size();
1189 },
1192 result.segment_offsets);
1193
1194 const int num_segments = segments_by_curve.total_size();
1195 result.segment_start_points.reinitialize(num_segments);
1196 result.segment_start_fractions.reinitialize(num_segments);
1197
1198 curve_mask.foreach_index(
1199 [&](const int curve_i) {
1200 const IndexRange points = points_by_curve[curve_i];
1201 const IndexMask curve_hit_mask = hit_mask.slice_content(points);
1202 const bool is_cyclic = cyclic[curve_i];
1203 const IndexRange segments = segments_by_curve[curve_i];
1204 const int hit_segments_start = (is_cyclic ? 0 : 1);
1205
1206 if (segments.is_empty()) {
1207 return;
1208 }
1209
1210 /* Add curve start a segment. */
1211 if (!is_cyclic) {
1212 result.segment_start_points[segments[0]] = points.first();
1213 result.segment_start_fractions[segments[0]] = 0.0f;
1214 }
1215
1216 curve_hit_mask.foreach_index([&](const int point_i, const int hit_i) {
1217 result.segment_start_points[segments[hit_segments_start + hit_i]] = point_i;
1218 result.segment_start_fractions[segments[hit_segments_start + hit_i]] =
1219 first_hit_factors[point_i];
1220 });
1221 },
1223
1224 return result;
1225}
1226
1227} // namespace ed::greasepencil
1228} // namespace blender
Low-level operations for curves.
Low-level operations for curves.
support for deformation groups and hooks.
Low-level operations for grease pencil.
A KD-tree for nearest neighbor search.
#define M_PI
#define GP_STROKE_MITER_ANGLE_ROUND
#define BLI_assert_unreachable()
#define ELEM(...)
SIMD_FORCE_INLINE btScalar angle(const btVector3 &v) const
Return the angle between this and another vector.
Definition btVector3.h:356
int64_t size() const
Definition BLI_array.hh:267
MutableSpan< T > as_mutable_span()
Definition BLI_array.hh:259
Array(Allocator allocator={}) noexcept
Definition BLI_array.hh:78
const T * data() const
Definition BLI_array.hh:323
IndexRange index_range() const
Definition BLI_array.hh:371
GPointer()=default
static IndexMask from_bools(Span< bool > bools, LinearAllocator<> &memory)
static IndexMask from_indices(Span< T > indices, LinearAllocator<> &memory)
constexpr int64_t first() const
constexpr IndexRange drop_back(int64_t n) const
constexpr int64_t last(const int64_t n=0) const
constexpr int64_t size() const
constexpr bool is_empty() const
constexpr int64_t start() const
constexpr IndexRange slice(int64_t start, int64_t size) const
constexpr IndexRange index_range() const
constexpr IndexRange drop_front(int64_t n) const
constexpr MutableSpan slice(const int64_t start, const int64_t size) const
Definition BLI_span.hh:579
constexpr void fill(const T &value) const
Definition BLI_span.hh:523
constexpr T & first() const
Definition BLI_span.hh:685
constexpr T & last(const int64_t n=0) const
Definition BLI_span.hh:695
constexpr Span slice(int64_t start, int64_t size) const
Definition BLI_span.hh:141
constexpr const T * data() const
Definition BLI_span.hh:219
constexpr const T & first() const
Definition BLI_span.hh:319
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
constexpr bool is_empty() const
Definition BLI_span.hh:264
bool is_empty() const
Definition BLI_stack.hh:310
void push(const T &value)
Definition BLI_stack.hh:215
int64_t size() const
void append(const T &value)
void append_n_times(const T &value, const int64_t n)
GAttributeReader lookup_or_default(StringRef name, AttrDomain domain, AttrType data_type, const void *default_value=nullptr) const
VArray< bool > cyclic() const
AttributeAccessor attributes() const
Span< float3 > positions() const
IndexRange curves_range() const
MutableSpan< int > offsets_for_write()
OffsetIndices< int > points_by_curve() const
const bke::CurvesGeometry & strokes() const
IndexMask slice_content(IndexRange range) const
void to_indices(MutableSpan< T > r_indices) const
void foreach_index(Fn &&fn, Mode mode=exec_mode::serial) const
#define FLT_MAX
#define layer
float length(VecOp< float, D >) RET
float3x3 scale(float3x3 mat, float2 scale)
void fill_index_range(MutableSpan< T > span, const T start=0)
void mix_groups(GSpan src, OffsetIndices< int > groups, Span< int > all_indices, std::optional< Span< float > > all_weights, GMutableSpan dst)
void update_custom_knot_modes(const IndexMask &mask, const KnotsMode mode_for_regular, const KnotsMode mode_for_cyclic, bke::CurvesGeometry &curves)
bke::CurvesGeometry copy_only_curve_domain(const bke::CurvesGeometry &src_curves)
void free(Subdiv *subdiv)
Definition subdiv.cc:192
void find_curve_intersections(const bke::CurvesGeometry &curves, const IndexMask &curve_mask, const Span< float2 > screen_space_positions, const Curves2DBVHTree &tree_data, const IndexRange tree_data_range, MutableSpan< bool > r_hits, std::optional< MutableSpan< float > > r_first_intersect_factors, std::optional< MutableSpan< float > > r_last_intersect_factors)
bke::CurvesGeometry curves_merge_by_distance(const bke::CurvesGeometry &src_curves, const float merge_distance, const IndexMask &selection, const bke::AttributeFilter &attribute_filter)
int64_t ramer_douglas_peucker_simplify(const IndexRange range, const float epsilon, const FunctionRef< float(int64_t, int64_t, int64_t)> dist_function, MutableSpan< bool > points_to_delete)
static void generate_circle_from_point(const float3 &pt, const float radius, const int corner_subdivisions, const int src_point_index, Vector< float3 > &r_perimeter, Vector< int > &r_src_indices)
static void generate_arc_from_point_to_point(const float3 &from, const float3 &to, const float3 &center_pt, const int corner_subdivisions, const int src_point_index, Vector< float3 > &r_perimeter, Vector< int > &r_src_indices)
void free_curves_2d_bvh_data(Curves2DBVHTree &data)
CurveSegmentsData find_curve_segments(const bke::CurvesGeometry &curves, const IndexMask &curve_mask, const Span< float2 > screen_space_positions, const Curves2DBVHTree &tree_data, const IndexRange tree_data_range)
static void generate_corner(const float3 &pt_a, const float3 &pt_b, const float3 &pt_c, const float radius, const float miter_limit_angle, const int corner_subdivisions, const int src_point_index, Vector< float3 > &r_perimeter, Vector< int > &r_src_indices)
IndexMask polyline_detect_corners(Span< float2 > points, const float radius_min, const float radius_max, const int samples_max, const float angle_threshold, IndexMaskMemory &memory)
static void generate_stroke_perimeter(const Span< float3 > all_positions, const Span< float > all_radii, const IndexRange points, const int corner_subdivisions, const bool is_cyclic, const bool use_caps, const eGPDstroke_Caps start_cap_type, const eGPDstroke_Caps end_cap_type, const VArray< float > miter_angles, const float outline_offset, Vector< float3 > &r_perimeter, Vector< int > &r_point_counts, Vector< int > &r_point_indices)
static void generate_cap(const float3 &point, const float3 &tangent, const float radius, const int corner_subdivisions, const eGPDstroke_Caps cap_type, const int src_point_index, Vector< float3 > &r_perimeter, Vector< int > &r_src_indices)
bke::CurvesGeometry curves_merge_endpoints_by_distance(const ARegion &region, const bke::CurvesGeometry &src_curves, const float4x4 &layer_to_world, const float merge_distance, const IndexMask &selection, const bke::AttributeFilter &attribute_filter)
Array< float2 > polyline_fit_curve(Span< float2 > points, const float error_threshold, const IndexMask &corner_mask)
Curves2DBVHTree build_curves_2d_bvh_from_visible(const ViewContext &vc, const Object &object, const GreasePencil &grease_pencil, Span< MutableDrawingInfo > drawings, const int frame_number)
int curve_merge_by_distance(const IndexRange points, const Span< float > distances, const IndexMask &selection, const float merge_distance, MutableSpan< int > r_merge_indices)
bke::CurvesGeometry create_curves_outline(const bke::greasepencil::Drawing &drawing, const IndexMask &strokes, const float4x4 &transform, const int corner_subdivisions, const float outline_radius, const float outline_offset, const int material_index)
constexpr ParallelGrainSize grain_size(int grain_size)
bke::CurvesGeometry curves_merge_endpoints(const bke::CurvesGeometry &src_curves, Span< int > connect_to_curve, Span< bool > flip_direction, const bke::AttributeFilter &attribute_filter)
T cos(const AngleRadianBase< T > &a)
isect_result< VecBase< T, Size > > isect_seg_seg(const VecBase< T, Size > &v1, const VecBase< T, Size > &v2, const VecBase< T, Size > &v3, const VecBase< T, Size > &v4)
T distance(const T &a, const T &b)
T length(const VecBase< T, Size > &a)
QuaternionBase< T > normalize_and_get_length(const QuaternionBase< T > &q, T &out_length)
T dot(const QuaternionBase< T > &a, const QuaternionBase< T > &b)
T average(const VecBase< T, Size > &a)
bool is_zero(const T &a)
CartesianBasis invert(const CartesianBasis &basis)
T atan2(const T &y, const T &x)
MatBase< T, NumCol, NumRow > normalize(const MatBase< T, NumCol, NumRow > &a)
VecBase< T, 3 > to_scale(const MatBase< T, NumCol, NumRow > &mat)
T sin(const AngleRadianBase< T > &a)
T abs(const T &a)
void transform_points(const float4x4 &transform, MutableSpan< float3 > points, bool use_threading=true)
OffsetIndices< int > accumulate_counts_to_offsets(MutableSpan< int > counts_to_offsets, int start_offset=0)
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
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void(*)(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit) BVHTree_RayCastCallback
void kdtree_balance(KDTree< CoordT > *tree)
__int64 int64_t
Definition BKE_text.h:90
unsigned int uint
Definition BKE_text.h:55
void BLI_bvhtree_free(BVHTree *tree)
int kdtree_find_nearest_cb(const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > *r_nearest, Filter &&filter_cb)
void BLI_bvhtree_balance(BVHTree *tree)
float2 ED_view3d_project_float_v2_m4(const ARegion *region, const float co[3], const float4x4 &mat)
MatBase< float, 4, 4 > float4x4
int BLI_bvhtree_ray_cast(const BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata)
@ NURBS_KNOT_MODE_NORMAL
KDTree< CoordT > * kdtree_new(uint nodes_len_capacity)
Definition BLI_kdtree.hh:65
VecBase< float, 2 > float2
BMesh const char void * data
void kdtree_insert(KDTree< CoordT > *tree, int index, const CoordT &co)
Definition BLI_kdtree.hh:96
BVHTree * BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
void kdtree_free(KDTree< CoordT > *tree)
Definition BLI_kdtree.hh:84
void BKE_defgroup_copy_list(ListBaseT< bDeformGroup > *outbase, const ListBaseT< bDeformGroup > *inbase)
Definition deform.cc:75
void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
int kdtree_calc_duplicates_fast(const KDTree< CoordT > *tree, const typename KDTree< CoordT >::ValueType range, const bool use_index_order, int *duplicates)
float4x4 ED_view3d_ob_project_mat_get_from_obmat(const RegionView3D *rv3d, const float4x4 &obmat)
VecBase< float, 3 > float3
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
signed char int8_t
Definition BKE_text.h:76
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
ListBaseT< struct bDeformGroup > vertex_group_names
RegionView3D * rv3d
Definition ED_view3d.hh:86