Blender V5.3
grease_pencil_segments_geom.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2025 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include <algorithm>
10#include <functional>
11
12#include "BLI_array.hh"
13#include "BLI_array_utils.hh"
14#include "BLI_bounds.hh"
15#include "BLI_lasso_2d.hh"
16#include "BLI_math_base.hh"
17#include "BLI_math_geom.hh"
19#include "BLI_offset_indices.hh"
20#include "BLI_sort.hh"
21#include "BLI_task.hh"
22#include "BLI_vector.hh"
23
24#include "BKE_curves.hh"
26
27#include "ED_grease_pencil.hh"
28#include "ED_view3d.hh"
29
31
33
34bool Segment::is_loop() const
35{
36 return full_wrap_loop;
37}
38
39bool Segment::has_intersection(const Side side) const
40{
41 return intersection_index[side] != -1;
42}
43
44int2 Segment::edge(const Side side) const
45{
46 return int2(points[side], this->wrap_index(points[side] + 1));
47}
48
49int Segment::wrap_index(const int i) const
50{
52}
53
55{
56 if (this->is_loop()) {
57 return src_points;
58 }
59
62 }
63
65 return src_points;
66 }
67
68 /* If both intersection points are on the same edge, there's ether no points between or
69 * all of the points are. */
71
72 /* If both intersections points are the same, either the segment as nothing or the full
73 * range. */
75 if (this->is_loop()) {
77 }
78 return IndexRange(0);
79 }
80
83 }
84 return IndexRange(0);
85 }
86
90 }
91
93}
94
96{
97 return this->point_range().size();
98}
99
100Segment Segment::from_curve(const int curve_i, const IndexRange points, const bool cyclic)
101{
103 segment.curve = curve_i;
104 segment.src_points = points;
105
106 segment.points[Side::Start] = points.first();
107 segment.points[Side::End] = points.last();
108
109 segment.intersection_factor[Side::Start] = 0.0f;
110 segment.intersection_factor[Side::End] = cyclic ? 1.0f : 0.0f;
111
112 segment.full_wrap_loop = cyclic;
113
114 return segment;
115}
116
118 const IndexRange points,
119 const std::optional<int> point_start,
120 const std::optional<int> point_end,
121 const std::optional<float> factor_start,
122 const std::optional<float> factor_end,
123 const std::optional<int> inter_index_start,
124 const std::optional<int> inter_index_end)
125{
127 segment.curve = curve_i;
128 segment.src_points = points;
129
130 if (point_start) {
131 segment.points[Side::Start] = *point_start;
132 segment.intersection_factor[Side::Start] = *factor_start;
133 }
134 else {
135 segment.points[Side::Start] = points.first();
136 segment.intersection_factor[Side::Start] = 0.0f;
137 }
138
139 if (inter_index_start) {
140 segment.intersection_index[Side::Start] = *inter_index_start;
141 }
142
143 if (point_end) {
144 segment.points[Side::End] = *point_end;
145 segment.intersection_factor[Side::End] = *factor_end;
146 }
147 else {
148 segment.points[Side::End] = points.last();
149 segment.intersection_factor[Side::End] = 0.0f;
150 }
151
152 if (inter_index_end) {
153 segment.intersection_index[Side::End] = *inter_index_end;
154 }
155
158
159 return segment;
160}
161
168 const float2 &co_b,
169 const float2 &co_c,
170 const float2 &co_d)
171{
172 /* Get intersection point. */
173 const float a1 = co_b[1] - co_a[1];
174 const float b1 = co_a[0] - co_b[0];
175 const float c1 = a1 * co_a[0] + b1 * co_a[1];
176
177 const float a2 = co_d[1] - co_c[1];
178 const float b2 = co_c[0] - co_d[0];
179 const float c2 = a2 * co_c[0] + b2 * co_c[1];
180
181 const float det = (a1 * b2 - a2 * b1);
182 if (det == 0.0f) {
183 return 0.0f;
184 }
185
186 const float2 isect((b2 * c1 - b1 * c2) / det, (a1 * c2 - a2 * c1) / det);
187
188 /* Get normalized distance from point a to intersection point. */
189 const float length_ab = math::distance(co_b, co_a);
190 const float distance = math::safe_divide(math::distance(isect, co_a), length_ab);
191
192 /* Snap to the ends if very close. */
193 if (math::abs(distance) < 0.0001f) {
194 return 0.0f;
195 }
196 if (math::abs(distance - 1.0f) < 0.0001f) {
197 return 1.0f;
198 }
199
200 return distance;
201}
202
204 const int point_j,
205 const float factor_i,
206 const float factor_j,
207 const int curve_i,
208 const int curve_j)
209{
210 IntersectionPoint inter_point;
211 inter_point.point_i = point_i;
212 inter_point.point_j = point_j;
213 inter_point.factor_i = factor_i;
214 inter_point.factor_j = factor_j;
215 inter_point.curve_i = curve_i;
216 inter_point.curve_j = curve_j;
217
218 return inter_point;
219}
220
222 const Span<float2> screen_space_positions,
223 const Span<Bounds<float2>> screen_space_bbox,
224 const OffsetIndices<int> points_by_curve,
225 const VArray<bool> &cyclic,
226 const IndexMask &visible_curves,
227 const int curve_i,
228 Array<Vector<int>> &r_inters_per_curves,
229 Vector<IntersectionPoint> &r_intersections)
230{
231 const bool cyclic_i = cyclic[curve_i];
232 const IndexRange curve_points_i = points_by_curve[curve_i];
233
234 for (const int i : curve_points_i.index_range().drop_back(cyclic_i ? 0 : 1)) {
235 const int point_i1 = curve_points_i[i];
236 const int point_i2 = curve_points_i[(i + 1) % curve_points_i.size()];
237
238 const float2 co_i1 = screen_space_positions[point_i1];
239 const float2 co_i2 = screen_space_positions[point_i2];
240
241 Bounds<float2> bbox_i{math::min(co_i1, co_i2), math::max(co_i1, co_i2)};
242 bbox_i.pad(BBOX_PADDING);
243
244 /* Add some padding to the line segment i1-i2, otherwise we could just miss an
245 * intersection. */
246 const float2 padding_i = math::normalize(co_i2 - co_i1);
247 const float2 padded_i1 = co_i1 - padding_i;
248 const float2 padded_i2 = co_i2 + padding_i;
249
250 visible_curves.foreach_index([&](const int curve_j) {
251 /* Because intersecting the curves i with j and j with i, we skip one half to avoid
252 * duplicating all the points. */
253 if (curve_i > curve_j) {
254 return;
255 }
256
257 /* Bounding box check: Skip curves that don't overlap segment i1-i2. */
258 if (!bounds::intersect(bbox_i, screen_space_bbox[curve_j]).has_value()) {
259 return;
260 }
261
262 const bool cyclic_j = cyclic[curve_j];
263 const IndexRange curve_points_j = points_by_curve[curve_j];
264
265 for (const int j : curve_points_j.index_range().drop_back(cyclic_j ? 0 : 1)) {
266 const int point_j1 = curve_points_j[j];
267 const int point_j2 = curve_points_j[(j + 1) % curve_points_j.size()];
268
269 /* Don't self check. */
270 if (curve_i == curve_j && (point_i1 == point_j1 || point_i1 == point_j2 ||
271 point_i2 == point_j1 || point_i2 == point_j2))
272 {
273 continue;
274 }
275
276 const float2 co_j1 = screen_space_positions[point_j1];
277 const float2 co_j2 = screen_space_positions[point_j2];
278
279 Bounds<float2> bbox_j{math::min(co_j1, co_j2), math::max(co_j1, co_j2)};
280 bbox_j.pad(BBOX_PADDING);
281
282 /* Skip when bounding boxes of i1-i2 and j1-j2 don't overlap. */
283 if (!bounds::intersect(bbox_i, bbox_j).has_value()) {
284 continue;
285 }
286
287 /* Add some padding to the line segment j1-j2, otherwise we could just miss an
288 * intersection. */
289 const float2 padding_j = math::normalize(co_j2 - co_j1);
290 const float2 padded_j1 = co_j1 - padding_j;
291 const float2 padded_j2 = co_j2 + padding_j;
292
293 /* Check for intersection. */
294 const auto isect = math::isect_seg_seg(padded_i1, padded_i2, padded_j1, padded_j2);
295 if (ELEM(isect.kind, isect.LINE_LINE_CROSS, isect.LINE_LINE_EXACT)) {
296 const float factor_i = get_intersection_distance_of_segments(co_i1, co_i2, co_j1, co_j2);
297 const float factor_j = get_intersection_distance_of_segments(co_j1, co_j2, co_i1, co_i2);
298
299 /* If the intersection is outside of the edge, skip it. Note that exactly on the edge is
300 * accepted. */
301 if (factor_i < 0.0f || factor_i > 1.0f || factor_j < 0.0f || factor_j > 1.0f) {
302 continue;
303 }
304
305 r_inters_per_curves[curve_i].append(r_intersections.size());
306 r_inters_per_curves[curve_j].append(r_intersections.size());
307 r_intersections.append(
308 create_intersection(point_i1, point_j1, factor_i, factor_j, curve_i, curve_j));
309 }
310 }
311 });
312 }
313}
314
315/* TODO: This method of finding intersections is O(N^2) and should replaced with something faster.
316 */
317void find_intersections_between_all_curves(const Span<float2> screen_space_positions,
318 const Span<Bounds<float2>> screen_space_bbox,
319 const OffsetIndices<int> points_by_curve,
320 const VArray<bool> &cyclic,
321 const IndexMask &visible_curves,
322 Array<Vector<int>> &r_inters_per_curves,
323 Vector<IntersectionPoint> &r_intersections)
324{
325 visible_curves.foreach_index([&](const int curve_i) {
326 find_intersections_between_curve_and_curves(screen_space_positions,
327 screen_space_bbox,
328 points_by_curve,
329 cyclic,
330 visible_curves,
331 curve_i,
332 r_inters_per_curves,
333 r_intersections);
334 });
335}
336
338 MutableSpan<IntersectionPoint> intersections)
339{
340 for (const int seg_i : all_segments.index_range()) {
341 const Segment &segment = all_segments[seg_i];
342 const int curve_i = segment.curve;
343
344 if (segment.has_intersection(Side::Start)) {
345 IntersectionPoint &inter_start = intersections[segment.intersection_index[Side::Start]];
346 if (curve_i == inter_start.curve_i) {
347 inter_start.segment_index_i[Side::End] = seg_i;
348 }
349 else {
350 inter_start.segment_index_j[Side::End] = seg_i;
351 }
352 }
353
354 if (segment.has_intersection(Side::End)) {
355 IntersectionPoint &inter_end = intersections[segment.intersection_index[Side::End]];
356 if (curve_i == inter_end.curve_i) {
357 inter_end.segment_index_i[Side::Start] = seg_i;
358 }
359 else {
360 inter_end.segment_index_j[Side::Start] = seg_i;
361 }
362 }
363 }
364}
365
367 const Span<Vector<int>> inters_per_curves,
368 const OffsetIndices<int> points_by_curve,
369 const Span<IntersectionPoint> &intersections,
370 const VArray<bool> &cyclic,
371 Vector<Segment> &all_segments)
372{
373 const IndexRange points_k = points_by_curve[curve_k];
374 const Span<int> inters = inters_per_curves[curve_k];
375
376 const int start_size = all_segments.size();
377
378 if (inters.size() == 0) {
379 all_segments.append(Segment::from_curve(curve_k, points_k, cyclic[curve_k]));
380 return 1;
381 }
382
383 if (inters.size() == 1 && cyclic[curve_k]) {
384 const int int_p = inters.first();
385
386 const IntersectionPoint &inter = intersections[int_p];
387
388 all_segments.append(Segment::from_intersections(curve_k,
389 points_k,
390 inter.point_for_curve(curve_k),
391 inter.point_for_curve(curve_k),
392 inter.factor_for_curve(curve_k),
393 inter.factor_for_curve(curve_k),
394 int_p,
395 int_p));
396 all_segments.last().full_wrap_loop = true;
397 return 1;
398 }
399
400 Array<int> inter_sorted_ids = Array<int>(inters.size());
401 array_utils::fill_index_range<int>(inter_sorted_ids);
402
403 parallel_sort(inter_sorted_ids.begin(), inter_sorted_ids.end(), [&](int i1, int i2) {
404 const IntersectionPoint &inter1 = intersections[inters[i1]];
405 const IntersectionPoint &inter2 = intersections[inters[i2]];
406 return inter1.parameter_for_curve(curve_k) < inter2.parameter_for_curve(curve_k);
407 });
408
409 if (cyclic[curve_k]) {
410 const int int_p_1 = inters[inter_sorted_ids.first()];
411 const int int_p_2 = inters[inter_sorted_ids.last()];
412
413 const IntersectionPoint &inter_first = intersections[int_p_1];
414 const IntersectionPoint &inter_last = intersections[int_p_2];
415
416 all_segments.append(Segment::from_intersections(curve_k,
417 points_k,
418 inter_last.point_for_curve(curve_k),
419 inter_first.point_for_curve(curve_k),
420 inter_last.factor_for_curve(curve_k),
421 inter_first.factor_for_curve(curve_k),
422 int_p_2,
423 int_p_1));
424 }
425 else {
426 const int int_p_1 = inters[inter_sorted_ids.first()];
427 const IntersectionPoint &inter_first = intersections[int_p_1];
428
429 if (inter_first.parameter_for_curve(curve_k) != float(points_k.first())) {
430 all_segments.append(Segment::from_intersections(curve_k,
431 points_k,
432 std::nullopt,
433 inter_first.point_for_curve(curve_k),
434 std::nullopt,
435 inter_first.factor_for_curve(curve_k),
436 std::nullopt,
437 int_p_1));
438 }
439 }
440
441 for (const int inter_id : inter_sorted_ids.index_range().drop_back(1)) {
442 const int int_p_1 = inters[inter_sorted_ids[inter_id]];
443 const int int_p_2 = inters[inter_sorted_ids[inter_id + 1]];
444
445 const IntersectionPoint &inter_first = intersections[int_p_1];
446 const IntersectionPoint &inter_last = intersections[int_p_2];
447
448 if (inter_first.parameter_for_curve(curve_k) != inter_last.parameter_for_curve(curve_k)) {
449 all_segments.append(Segment::from_intersections(curve_k,
450 points_k,
451 inter_first.point_for_curve(curve_k),
452 inter_last.point_for_curve(curve_k),
453 inter_first.factor_for_curve(curve_k),
454 inter_last.factor_for_curve(curve_k),
455 int_p_1,
456 int_p_2));
457 }
458 }
459
460 if (!cyclic[curve_k]) {
461 const int int_p_2 = inters[inter_sorted_ids.last()];
462 const IntersectionPoint &inter_last = intersections[int_p_2];
463
464 if (inter_last.parameter_for_curve(curve_k) != float(points_k.last())) {
465 all_segments.append(Segment::from_intersections(curve_k,
466 points_k,
467 inter_last.point_for_curve(curve_k),
468 std::nullopt,
469 inter_last.factor_for_curve(curve_k),
470 std::nullopt,
471 int_p_2,
472 std::nullopt));
473 }
474 }
475
476 return all_segments.size() - start_size;
477}
478
480 const OffsetIndices<int> points_by_curve,
481 const Span<IntersectionPoint> &intersections,
482 const VArray<bool> &cyclic,
483 Vector<Segment> &all_segments,
484 MutableSpan<int> segments_num_per_curve)
485{
486 for (const int curve_k : points_by_curve.index_range()) {
487 segments_num_per_curve[curve_k] = create_segments_from_intersections_single_curve(
488 curve_k, inters_per_curves, points_by_curve, intersections, cyclic, all_segments);
489 }
490}
491
492static bool check_and_join_segments(Segment &first, const Segment &second)
493{
494 if (first.curve != second.curve) {
495 return false;
496 }
497
498 const float parameter_first_start = first.points[Side::Start] +
500 const float parameter_first_end = first.points[Side::End] + first.intersection_factor[Side::End];
501 const float parameter_second_start = second.points[Side::Start] +
503 const float parameter_second_end = second.points[Side::End] +
505
506 if ((parameter_first_end == parameter_second_start) ||
508 first.intersection_index[Side::End] != -1))
509 {
510 first.points[Side::End] = second.points[Side::End];
513
514 return true;
515 }
516 if ((parameter_first_start == parameter_second_end) ||
518 first.intersection_index[Side::Start] != -1))
519 {
520 first.points[Side::Start] = second.points[Side::Start];
523
524 return true;
525 }
526
527 return false;
528}
529
531 const Span<Segment> segments,
532 const Span<bool> segment_reversed,
533 const Span<bool> cyclic,
534 const OffsetIndices<int> segment_offsets)
535{
537
538 bke::SpanAttributeWriter dst_start_caps = dst_attributes.lookup_or_add_for_write_span<int8_t>(
539 "start_cap", bke::AttrDomain::Curve);
540 bke::SpanAttributeWriter dst_end_caps = dst_attributes.lookup_or_add_for_write_span<int8_t>(
541 "end_cap", bke::AttrDomain::Curve);
542
543 threading::parallel_for(segment_offsets.index_range(), 4096, [&](const IndexRange curves) {
544 for (const int curve_i : curves) {
545 /* If the curve is cyclic, don't cut it. */
546 if (cyclic[curve_i]) {
547 continue;
548 }
549
550 const IndexRange segment_range = segment_offsets[curve_i];
551
552 const int segment_index_first = segment_range.first();
553 const bool reversed_first = segment_reversed[segment_index_first];
554 const Segment &segment_first = segments[segment_index_first];
555 const Side direction_first = reversed_first ? Side::End : Side::Start;
556 const int inter_index_first = segment_first.intersection_index[direction_first];
557
558 const int segment_index_last = segment_range.last();
559 const bool reversed_last = segment_reversed[segment_index_last];
560 const Segment &segment_last = segments[segment_index_last];
561 const Side direction_last = reversed_last ? Side::Start : Side::End;
562 const int inter_index_last = segment_last.intersection_index[direction_last];
563
564 /* Check if there is a intersection and therefore the curve should be cut. */
565 if (inter_index_first != -1) {
566 dst_start_caps.span[curve_i] = GP_STROKE_CAP_TYPE_FLAT;
567 }
568 if (inter_index_last != -1) {
569 dst_end_caps.span[curve_i] = GP_STROKE_CAP_TYPE_FLAT;
570 }
571 }
572 });
573
574 dst_start_caps.finish();
575 dst_end_caps.finish();
576}
577
578/* We store the side as sign, but because a segment with index zero is valid, we shift by one. */
580{
581 return side == Side::Start ? index + 1 : -(index + 1);
582}
583
585{
586 return math::abs(encoded) - 1;
587}
588
590{
591 return encoded < 0 ? Side::End : Side::Start;
592}
593
595 const Span<bool> segments_to_keep,
596 const VArray<bool> &is_cyclic,
597 MutableSpan<SegmentConnections> segment_connections)
598{
599
600 threading::parallel_for(segments_by_curve.index_range(), 4096, [&](const IndexRange curves) {
601 for (const int curve_i : curves) {
602 const IndexRange segment_range = segments_by_curve[curve_i];
603
604 if (segment_range.size() == 1) {
605 if (segments_to_keep[segment_range.first()]) {
606 segment_connections[segment_range.first()][Side::Start] = SEGMENT_CONNECTION_NULL;
607 segment_connections[segment_range.first()][Side::End] = SEGMENT_CONNECTION_NULL;
608 }
609 continue;
610 }
611
612 for (const int segment_i : segment_range.drop_back(1)) {
613 if (!segments_to_keep[segment_i]) {
614 continue;
615 }
616
617 if (segments_to_keep[segment_i + 1]) {
618 segment_connections[segment_i][Side::End] = encode_index_and_side(segment_i + 1,
619 Side::Start);
620 segment_connections[segment_i + 1][Side::Start] = encode_index_and_side(segment_i,
621 Side::End);
622 }
623 else {
624 segment_connections[segment_i][Side::End] = SEGMENT_CONNECTION_NULL;
625 }
626 }
627
628 if (!segments_to_keep[segment_range.last()]) {
629 continue;
630 }
631
632 if (!is_cyclic[curve_i]) {
633 segment_connections[segment_range.first()][Side::Start] = SEGMENT_CONNECTION_NULL;
634 segment_connections[segment_range.last()][Side::End] = SEGMENT_CONNECTION_NULL;
635 continue;
636 }
637
638 if (segments_to_keep[segment_range.first()]) {
639 segment_connections[segment_range.first()][Side::Start] = encode_index_and_side(
640 segment_range.last(), Side::End);
641 segment_connections[segment_range.last()][Side::End] = encode_index_and_side(
642 segment_range.first(), Side::Start);
643 }
644 else {
645 segment_connections[segment_range.last()][Side::End] = SEGMENT_CONNECTION_NULL;
646 }
647 }
648 });
649}
650
652 const Span<bool> segments_to_keep,
653 const Span<SegmentConnections> segment_connections,
654 Vector<Segment> &segments,
655 Vector<int> &segment_offset_data,
656 Vector<bool> &segment_reversed,
657 Vector<bool> &cyclic)
658{
659 BLI_assert(all_segments.size() == segments_to_keep.size());
660 BLI_assert(all_segments.size() == segment_connections.size());
661
662 segment_offset_data.append(0);
663
664 Array<bool> processed_segments(all_segments.size(), false);
665 int start_segment = 0;
666
667 auto get_next_unprocessed_segment = [&]() {
668 /* All segment before `start_segment` are guaranteed to be processed, so skip search them.
669 * This optimization make the algorithm `O(N)` instead of `O(N^2)`.*/
670 const int empty_num = start_segment;
671 const int first_segment = processed_segments.as_span().drop_front(empty_num).first_index_try(
672 false);
673
674 if (first_segment == -1) {
675 return -1;
676 }
677 return first_segment + empty_num;
678 };
679
680 /* Mark all segments that are not to keep as processed. */
681 for (const int seg_i : all_segments.index_range()) {
682 if (!segments_to_keep[seg_i]) {
683 processed_segments[seg_i] = true;
684 }
685 }
686
687 start_segment = get_next_unprocessed_segment();
688
689 /* Follow each segment until it loops or ends. */
690 while (start_segment != -1) {
691 Vector<Segment> curve_segments;
692 Vector<bool> curve_segment_reversed;
693
694 auto append_segment = [&](const Segment &current_segment, const bool current_backwards) {
695 if (curve_segments.size() == 0) {
696 curve_segments.append(current_segment);
697 curve_segment_reversed.append(current_backwards);
698 return;
699 }
700 /* Check if the last segment can be joined with this one. */
701 if (!check_and_join_segments(curve_segments.last(), current_segment)) {
702 curve_segments.append(current_segment);
703 curve_segment_reversed.append(current_backwards);
704 }
705 };
706
707 /* Loop backwards to find the first segment. */
708 bool current_backwards = true;
709 int current_i = start_segment;
710 bool curve_done = false;
711 while (!curve_done) {
712 const EncodedConnection next_encoded =
713 segment_connections[current_i][current_backwards ? Side::Start : Side::End];
714
715 if (next_encoded == SEGMENT_CONNECTION_NULL) {
716 curve_done = true;
717 break;
718 }
719
720 const int next_segment = decode_index(next_encoded);
721 const Side next_side = decode_side(next_encoded);
722
723 current_i = next_segment;
724 current_backwards = next_side == Side::End;
725
726 if (next_segment == start_segment) {
727 curve_done = true;
728 break;
729 }
730 }
731
732 /* Reverse the direction. */
733 current_backwards = !current_backwards;
734 const int first_segment = current_i;
735
736 /* Loop through forwards, adding segments until ending or looping. */
737 curve_done = false;
738 bool curve_closed = false;
739 while (!curve_done) {
740 if (processed_segments[current_i] == true) {
742 break;
743 }
744
745 const Segment &current_segment = all_segments[current_i];
746 processed_segments[current_i] = true;
747 append_segment(current_segment, current_backwards);
748
749 const EncodedConnection next_encoded =
750 segment_connections[current_i][current_backwards ? Side::Start : Side::End];
751
752 if (next_encoded == SEGMENT_CONNECTION_NULL) {
753 curve_done = true;
754 curve_closed = false;
755 if (curve_segments.size() == 1) {
756 curve_closed = curve_segments.last().is_loop();
757 }
758 break;
759 }
760
761 const int next_segment = decode_index(next_encoded);
762 const Side next_side = decode_side(next_encoded);
763
764 /* Check if we are back to the start. */
765 if (next_segment == first_segment) {
766 curve_done = true;
767 curve_closed = true;
768
769 BLI_assert(next_side == Side::Start);
770
771 /* Check if the last segment can be joined to the first one. */
772 if (curve_segments.size() == 1) {
773 Segment &segment = curve_segments.last();
774
775 const float parameter_start = segment.points[Side::Start] +
776 segment.intersection_factor[Side::Start];
777 const float parameter_end = segment.points[Side::End] +
778 segment.intersection_factor[Side::End];
779
780 if ((parameter_end == parameter_start) ||
781 (segment.intersection_index[Side::End] == segment.intersection_index[Side::Start] &&
782 segment.intersection_index[Side::End] != -1))
783 {
784 if (segment.intersection_factor[Side::Start] == segment.intersection_factor[Side::End])
785 {
786 segment.full_wrap_loop = true;
787 }
788 }
789 break;
790 }
791 if (check_and_join_segments(curve_segments.first(), curve_segments.last())) {
792 curve_segments.remove_last();
793 curve_segment_reversed.remove_last();
794 }
795
796 break;
797 }
798
799 BLI_assert(segments_to_keep[next_segment]);
800 BLI_assert(!processed_segments[next_segment]);
801
802 current_i = next_segment;
803 current_backwards = next_side == Side::End;
804 }
805
806 segments.extend(curve_segments);
807 segment_reversed.extend(curve_segment_reversed);
808
809 segment_offset_data.append(segments.size());
810 cyclic.append(curve_closed);
811
812 start_segment = get_next_unprocessed_segment();
813 }
814}
815
816void compute_bounding_boxes(const OffsetIndices<int> src_points_by_curve,
817 const Span<float2> screen_space_positions,
818 MutableSpan<Bounds<float2>> screen_space_bbox)
819{
821 src_points_by_curve.index_range(), 512, [&](const IndexRange src_curves) {
822 for (const int src_curve : src_curves) {
823 Bounds<float2> &bbox = screen_space_bbox[src_curve];
824
825 const IndexRange src_points = src_points_by_curve[src_curve];
826 bbox = *bounds::min_max(screen_space_positions.slice(src_points));
827
828 /* Add some padding, otherwise we could just miss intersections. */
829 bbox.pad(BBOX_PADDING);
830 }
831 });
832}
833
834void compute_bounding_boxes(const OffsetIndices<int> src_points_by_curve,
835 const GroupedSpan<int> shapes,
836 const Span<float2> screen_space_positions,
837 MutableSpan<Bounds<float2>> screen_space_bbox)
838{
839 threading::parallel_for(shapes.index_range(), 512, [&](const IndexRange shape_ids) {
840 for (const int shape_id : shape_ids) {
841 std::optional<Bounds<float2>> bbox;
842
843 const Span<int> shape = shapes[shape_id];
844 for (const int curve_i : shape) {
845 const IndexRange src_points = src_points_by_curve[curve_i];
846 bbox = bounds::merge(bbox, *bounds::min_max(screen_space_positions.slice(src_points)));
847 }
848
849 /* Add some padding, otherwise we could just miss intersections. */
850 bbox->pad(BBOX_PADDING);
851
852 screen_space_bbox[shape_id] = *bbox;
853 }
854 });
855}
856
857} // namespace blender::ed::greasepencil::segment
Low-level operations for curves.
#define BLI_assert_unreachable()
#define ELEM(...)
Span< T > as_span() const
Definition BLI_array.hh:254
const T * end() const
Definition BLI_array.hh:336
const T & last(const int64_t n=0) const
Definition BLI_array.hh:307
IndexRange index_range() const
Definition BLI_array.hh:371
const T & first() const
Definition BLI_array.hh:292
const T * begin() const
Definition BLI_array.hh:332
constexpr int64_t first() const
constexpr IndexRange shift(int64_t n) 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 IndexRange()=default
constexpr bool contains(int64_t value) const
constexpr IndexRange index_range() const
static constexpr IndexRange from_begin_end_inclusive(const int64_t begin, const int64_t last)
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
int64_t size() const
void append(const T &value)
const T & last(const int64_t n=0) const
void extend(Span< T > array)
const T & first() const
MutableAttributeAccessor attributes_for_write()
GSpanAttributeWriter lookup_or_add_for_write_span(StringRef name, AttrDomain domain, AttrType data_type, const AttributeInit &initializer=AttributeInitDefaultValue())
static Segment from_curve(int curve_i, IndexRange points, bool cyclic)
static Segment from_intersections(int curve_i, IndexRange points, const std::optional< int > point_start, const std::optional< int > point_end, const std::optional< float > factor_start, const std::optional< float > factor_end, const std::optional< int > inter_index_start, const std::optional< int > inter_index_end)
void foreach_index(Fn &&fn, Mode mode=exec_mode::serial) const
float distance(float, float) RET
void fill_index_range(MutableSpan< T > span, const T start=0)
std::optional< Bounds< T > > intersect(const Bounds< T > &a, const Bounds< T > &b)
void cut_caps(bke::CurvesGeometry &dst, const Span< Segment > segments, const Span< bool > segment_reversed, const Span< bool > cyclic, const OffsetIndices< int > segment_offsets)
EncodedConnection encode_index_and_side(const int index, const Side side)
static void find_intersections_between_curve_and_curves(const Span< float2 > screen_space_positions, const Span< Bounds< float2 > > screen_space_bbox, const OffsetIndices< int > points_by_curve, const VArray< bool > &cyclic, const IndexMask &visible_curves, const int curve_i, Array< Vector< int > > &r_inters_per_curves, Vector< IntersectionPoint > &r_intersections)
void compute_bounding_boxes(const OffsetIndices< int > src_points_by_curve, const Span< float2 > screen_space_positions, MutableSpan< Bounds< float2 > > screen_space_bbox)
IntersectionPoint create_intersection(const int point_i, const int point_j, const float factor_i, const float factor_j, const int curve_i, const int curve_j)
void create_segments_from_intersections(const Span< Vector< int > > inters_per_curves, const OffsetIndices< int > points_by_curve, const Span< IntersectionPoint > &intersections, const VArray< bool > &cyclic, Vector< Segment > &all_segments, MutableSpan< int > segments_num_per_curve)
void store_segment_map_on_intersections(const Span< Segment > all_segments, MutableSpan< IntersectionPoint > intersections)
int decode_index(const EncodedConnection encoded)
int create_segments_from_intersections_single_curve(const int curve_k, const Span< Vector< int > > inters_per_curves, const OffsetIndices< int > points_by_curve, const Span< IntersectionPoint > &intersections, const VArray< bool > &cyclic, Vector< Segment > &all_segments)
Side decode_side(const EncodedConnection encoded)
void follow_segment_connections(const Span< Segment > all_segments, const Span< bool > segments_to_keep, const Span< SegmentConnections > segment_connections, Vector< Segment > &segments, Vector< int > &segment_offset_data, Vector< bool > &segment_reversed, Vector< bool > &cyclic)
static float get_intersection_distance_of_segments(const float2 &co_a, const float2 &co_b, const float2 &co_c, const float2 &co_d)
static bool check_and_join_segments(Segment &first, const Segment &second)
void find_intersections_between_all_curves(const Span< float2 > screen_space_positions, const Span< Bounds< float2 > > screen_space_bbox, const OffsetIndices< int > points_by_curve, const VArray< bool > &cyclic, const IndexMask &visible_curves, Array< Vector< int > > &r_inters_per_curves, Vector< IntersectionPoint > &r_intersections)
void create_connections_from_curves(const OffsetIndices< int > segments_by_curve, const Span< bool > segments_to_keep, const VArray< bool > &is_cyclic, MutableSpan< SegmentConnections > segment_connections)
T safe_divide(const T &a, const T &b)
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 min(const T &a, const T &b)
MatBase< T, NumCol, NumRow > normalize(const MatBase< T, NumCol, NumRow > &a)
T mod_periodic(const T &a, const T &b)
T max(const T &a, const T &b)
T abs(const T &a)
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
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void parallel_sort(RandomAccessIterator begin, RandomAccessIterator end)
Definition BLI_sort.hh:37
VecBase< int32_t, 2 > int2
VecBase< float, 2 > float2
signed char int8_t
Definition BKE_text.h:76
void pad(const PaddingT &padding)