Blender V5.3
grease_pencil_boolean.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2026 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
34using namespace segment;
35
36/* Calculate the winding order of a point when compared against a triangle. */
37static float point_in_tri_winding(const float2 pt,
38 const float2 v1,
39 const float2 v2,
40 const float2 v3)
41{
42 const float side12 = line_point_side_v2(v1, v2, pt);
43 const float side23 = line_point_side_v2(v2, v3, pt);
44 const float side31 = line_point_side_v2(v3, v1, pt);
45
46 /* The point is on an edge. */
47 if ((side12 == 0.0f && side23 >= 0.0f && side31 >= 0.0f) ||
48 (side12 >= 0.0f && side23 == 0.0f && side31 >= 0.0f) ||
49 (side12 >= 0.0f && side23 >= 0.0f && side31 == 0.0f))
50 {
51 return 0.5f;
52 }
53 if ((side12 == 0.0f && side23 <= 0.0f && side31 <= 0.0f) ||
54 (side12 <= 0.0f && side23 == 0.0f && side31 <= 0.0f) ||
55 (side12 <= 0.0f && side23 <= 0.0f && side31 == 0.0f))
56 {
57 return -0.5f;
58 }
59
60 /* The point is inside. */
61 if (side12 >= 0.0f && side23 >= 0.0f && side31 >= 0.0f) {
62 return 1.0f;
63 }
64 if (side12 <= 0.0f && side23 <= 0.0f && side31 <= 0.0f) {
65 return -1.0f;
66 }
67
68 /* The point is outside. */
69 return 0.0f;
70}
71
72/* Point must not be on a corner, but can be on an edge. */
73static int point_in_polygon_winding_twice(const float2 &point, const Span<float2> poly)
74{
75 /* Double and store as a int to avoid float rounding. */
76 int twice_winding = 0;
77 const float2 &tri_p1 = poly[0];
78 for (const int i : poly.index_range().drop_front(1).drop_back(1)) {
79 const float2 &tri_p2 = poly[i];
80 const float2 &tri_p3 = poly[i + 1];
81 twice_winding += int(point_in_tri_winding(point, tri_p1, tri_p2, tri_p3) * 2);
82 }
83 return twice_winding;
84}
85
86/* Point must not be on a corner or edge. */
87static int point_in_polygon_winding_int(const float2 &point, const Span<float2> poly)
88{
89 const int twice_winding = point_in_polygon_winding_twice(point, poly);
90 return int(twice_winding / 2);
91}
92
97 private:
98 /* Winding order of each curve. */
99 Map<int, int> orders_per_curve_;
100
101 public:
102 void add_to_curve(const int curve_i, const int winding_i)
103 {
104 if (winding_i == 0) {
105 return;
106 }
107
108 if (orders_per_curve_.contains(curve_i)) {
109 orders_per_curve_.lookup(curve_i) += winding_i;
110 }
111 else {
112 orders_per_curve_.add(curve_i, winding_i);
113 }
114 }
115
117 {
118 auto it_begin = orders_per_curve_.items().begin();
119 auto it_end = orders_per_curve_.items().end();
120 for (auto it = it_begin; it != it_end; it++) {
121 if ((*it).value == 0) {
122 orders_per_curve_.remove(it);
123 }
124 }
125 }
126
127 bool is_in_shape(const int shape_id, const GroupedSpan<int> &shapes) const
128 {
129 int winding = 0;
130
131 const Span<int> shape = shapes[shape_id];
132 for (const int curve_i : shape) {
133 if (orders_per_curve_.contains(curve_i)) {
134 winding += orders_per_curve_.lookup(curve_i);
135 }
136 }
137 /* Odd-Even fill rule. */
138 return winding % 2 != 0;
139 }
140
141 bool is_in_shapes(const IndexMask &shape_mask, const GroupedSpan<int> &shapes) const
142 {
143 if (orders_per_curve_.is_empty() || shape_mask.is_empty()) {
144 return false;
145 }
146
148 shape_mask.index_range(),
149 4096,
150 false,
151 [&](const IndexRange range, bool value) {
152 if (value) {
153 return value;
154 }
155 shape_mask.slice(range).foreach_index([&](const int shape_i) {
156 if (this->is_in_shape(shape_i, shapes)) {
157 value = true;
158 return;
159 }
160 });
161 return value;
162 },
163 std::logical_or());
164 }
165
166 /* Returns true if the point exists for this boolean operation. */
168 const GroupedSpan<int> &shapes,
169 const int subject_shape,
170 const IndexMask &clipping_shapes) const
171 {
172 const bool subj = this->is_in_shape(subject_shape, shapes);
173 const bool clip = this->is_in_shapes(clipping_shapes, shapes);
174
175 switch (op_params.boolean_mode) {
177 return subj && clip;
178 }
180 return subj && !clip;
181 }
182 case Operation::Union: {
183 return subj || clip;
184 }
185 default:
187 break;
188 }
189
190 return false;
191 }
192};
193
194/* The distance the left and right points will be placed from the segment.
195 * A to much smaller will cause floating point problems, but anything much larger can cause
196 * inaccuracies. */
197constexpr float epsilon_distance = 0.01f;
198/* When the segment is vary small the #epsilon_distance can be to large, instead use a factor of
199 * the segment's length. */
200constexpr float epsilon_factor = 0.05f;
201/* Factor along the segment where the left and right points are placed.
202 * A value of 0.5 can cause failure, so instead use a random number between 0.0 and 1.0 */
203constexpr float mid_point_factor = 0.35421f;
204
205/* Calculate the winding states for left and right of the segment. */
206static std::pair<WindingState, WindingState> LR_states_from_segment(
207 const Segment &segment,
208 const Span<float2> all_positions,
209 const OffsetIndices<int> points_by_curve,
210 const GroupedSpan<int> shapes,
211 const IndexMask &mask_shapes,
212 const VArray<bool> &is_fill)
213{
214 WindingState state_L;
215 WindingState state_R;
216
217 const int curve_i = segment.curve;
218
219 float2 point1;
220 float2 point2;
221
222 if (segment.has_intersection(Side::Start)) {
223 point1 = math::interpolate(all_positions[segment.edge(Side::Start)[0]],
224 all_positions[segment.edge(Side::Start)[1]],
225 segment.intersection_factor[Side::Start]);
226 }
227 else {
228 point1 = all_positions[segment.src_points.first()];
229 }
230
231 if (segment.edge(Side::Start)[0] == segment.edge(Side::End)[0] &&
232 (segment.points_num() == 0 ||
233 (segment.points_num() == 1 &&
234 (!segment.has_intersection(Side::Start) && segment.has_intersection(Side::End)))))
235 {
236 point2 = math::interpolate(all_positions[segment.edge(Side::End)[0]],
237 all_positions[segment.edge(Side::End)[1]],
238 segment.intersection_factor[Side::End]);
239 }
240 else {
241 const int first_end_index = segment.edge(Side::Start)[1];
242 int end_index = first_end_index;
243
244 point2 = all_positions[end_index];
245
246 /* If the points are on top of each other, go to the next point. */
247 while (math::distance(point1, point2) < 0.001f) {
248 end_index = segment.wrap_index(end_index + 1);
249 point2 = all_positions[end_index];
250
251 /* Prevent looping forever. */
252 if (end_index == first_end_index) {
253 break;
254 }
255 }
256 }
257
258 const float2 line_dir = math::normalize(point2 - point1);
259 /* Direction to the left. */
260 const float2 tan_dir = float2(-line_dir.y, line_dir.x);
261
262 const float2 mid_point = math::interpolate(point1, point2, mid_point_factor);
263
264 const float eps_dis = math::min(epsilon_factor * math::distance(point1, point2),
266
267 const float2 l_point = mid_point + tan_dir * eps_dis;
268 const float2 r_point = mid_point - tan_dir * eps_dis;
269
270 mask_shapes.foreach_index([&](const int shape_j_index) {
271 const Span<int> shape_j = shapes[shape_j_index];
272 for (const int curve_j : shape_j) {
273 if (curve_j == curve_i) {
274 return;
275 }
276
277 const IndexRange points_j = points_by_curve[curve_j];
278
279 const Span<float2> poly_j = all_positions.slice(points_j);
280
281 const int l_winding_i = point_in_polygon_winding_int(l_point, poly_j);
282 const int r_winding_i = point_in_polygon_winding_int(r_point, poly_j);
283
284 state_L.add_to_curve(curve_j, l_winding_i);
285 state_R.add_to_curve(curve_j, r_winding_i);
286 }
287 });
288
289 /* Self check. */
290 if (is_fill[curve_i]) {
291 const IndexRange points_i = points_by_curve[curve_i];
292
293 const Span<float2> poly_i = all_positions.slice(points_i);
294
295 const int l_winding_i = point_in_polygon_winding_int(l_point, poly_i);
296 const int r_winding_i = point_in_polygon_winding_int(r_point, poly_i);
297
298 state_L.add_to_curve(curve_i, l_winding_i);
299 state_R.add_to_curve(curve_i, r_winding_i);
300 }
301
302 state_L.remove_unneeded_ids();
303 state_R.remove_unneeded_ids();
304
305 return {state_L, state_R};
306}
307
308/* Check the left and right of a curve `k` */
310 const int curve_k,
311 const bool is_subj,
312 const int subj_shape_i,
313 const Span<float2> points,
314 const GroupedSpan<int> shapes,
315 const OffsetIndices<int> points_by_curve,
316 const IndexMask &clipping_shapes,
317 const Span<Segment> all_segments,
318 const OffsetIndices<int> segments_by_curve,
319 const VArray<bool> &is_fill,
320 MutableSpan<bool> all_inside_left,
321 MutableSpan<bool> all_inside_right)
322{
323 const IndexRange segments = segments_by_curve[curve_k];
324
325 if (segments.is_empty()) {
326 return;
327 }
328
329 const IndexMask &mask_shapes = is_subj ? clipping_shapes :
330 (!is_fill[shapes[subj_shape_i].first()] ?
331 IndexRange(0) :
332 IndexRange::from_single(subj_shape_i));
333
334 for (const int seg_i : segments) {
335 const Segment &this_segment = all_segments[seg_i];
336
337 auto [state_L, state_R] = LR_states_from_segment(
338 this_segment, points, points_by_curve, shapes, mask_shapes, is_fill);
339
340 if (is_fill[curve_k]) {
341 all_inside_left[seg_i] = state_L.is_contributing(
342 op_params, shapes, subj_shape_i, clipping_shapes);
343 all_inside_right[seg_i] = state_R.is_contributing(
344 op_params, shapes, subj_shape_i, clipping_shapes);
345 }
346 else {
347 all_inside_left[seg_i] = state_L.is_in_shapes(clipping_shapes, shapes);
348 all_inside_right[seg_i] = state_R.is_in_shapes(clipping_shapes, shapes);
349 }
350 }
351}
352
365 const Span<bool> unchanged_curves,
366 const ProjectionFunc project_fn)
367{
368 const OffsetIndices<int> points_by_curve = dst.points_by_curve();
370 bke::SpanAttributeWriter<int> fill_ids = attributes.lookup_for_write_span<int>("fill_id");
371
372 Array<float2> dst_positions_2d(dst.points_num());
373 const Span<float3> positions = dst.positions();
374 for (const int i : dst.points_range()) {
375 dst_positions_2d[i] = project_fn(positions[i]);
376 }
377
378 /* Returns if #curve_i in inside of #curve_j, only valid if the curves do not intersect. */
379 auto is_curve_i_in_j = [&](const int curve_i, const int curve_j) {
380 const IndexRange points_i = points_by_curve[curve_i];
381 const IndexRange points_j = points_by_curve[curve_j];
382
383 const Span<float2> poly_i = dst_positions_2d.as_span().slice(points_i);
384 const Span<float2> poly_j = dst_positions_2d.as_span().slice(points_j);
385
386 const int winding = point_in_polygon_winding_int(poly_i.first(), poly_j);
387
388 return winding % 2 != 0;
389 };
390
391 Array<bool> is_curve_child(points_by_curve.size(), false);
392 Array<Vector<int>> curve_children(points_by_curve.size());
393
394 for (const int curve_i : points_by_curve.index_range()) {
395 /* Skip curves without fill. */
396 if (fill_ids.span[curve_i] == 0) {
397 continue;
398 }
399
400 for (const int curve_j : points_by_curve.index_range()) {
401 if (curve_j == curve_i) {
402 continue;
403 }
404
405 if (fill_ids.span[curve_j] != fill_ids.span[curve_i]) {
406 continue;
407 }
408
409 if (is_curve_i_in_j(curve_i, curve_j)) {
410 is_curve_child[curve_i] = true;
411 curve_children[curve_j].append(curve_i);
412 }
413 }
414 }
415
416 int new_fill_id = bke::greasepencil::get_next_available_fill_id(fill_ids.span.varray());
417
418 for (const int curve_i : points_by_curve.index_range()) {
419 if (is_curve_child[curve_i]) {
420 continue;
421 }
422
423 if (fill_ids.span[curve_i] == 0 || unchanged_curves[curve_i]) {
424 continue;
425 }
426
427 fill_ids.span[curve_i] = new_fill_id;
428
429 const Span<int> curve_i_children = curve_children[curve_i];
430 for (const int curve_j : curve_i_children) {
431 fill_ids.span[curve_j] = new_fill_id;
432 }
433
434 new_fill_id++;
435 }
436
437 fill_ids.finish();
438}
439
462
463static int intersect(const float2 &P1,
464 const float2 &P2,
465 const float2 &Q1,
466 const float2 &Q2,
467 float *r_alpha_P,
468 float *r_alpha_Q)
469{
470 double r_lambda;
471 double r_mu;
472 const int val = isect_seg_seg_v2_lambda_mu_db(
473 double2(P1), double2(P2), double2(Q1), double2(Q2), &r_lambda, &r_mu);
474
475 *r_alpha_P = r_lambda;
476 *r_alpha_Q = r_mu;
477
478 return val;
479}
480
490
491 void append_result(const BooleanResult &other_result, const int subj_first_curve)
492 {
493 if (other_result.segments.is_empty()) {
494 return;
495 }
496
497 for (const int i : other_result.segment_offsets.index_range().drop_front(1)) {
499 }
500 cyclic.extend(other_result.cyclic);
502 subj_first_curves.append_n_times(subj_first_curve, other_result.cyclic.size());
503
504 for (const int i : other_result.segments.index_range()) {
505 segments.append(std::move(other_result.segments[i]));
506 }
507 }
508};
509
511 const Span<float2> points_j,
512 const int curve_i,
513 const int curve_j,
514 const bool cyclic_i,
515 const bool cyclic_j,
516 const int point_offset_i,
517 const int point_offset_j,
518 Array<Vector<int>> &r_inters_per_curves,
519 Vector<IntersectionPoint> &r_intersections)
520{
521 for (const int i : points_i.index_range().drop_back(cyclic_i ? 0 : 1)) {
522 for (const int j : points_j.index_range().drop_back(cyclic_j ? 0 : 1)) {
523 float alpha_a, alpha_b;
524 const int val = intersect(points_i[i],
525 points_i[(i + 1) % points_i.size()],
526 points_j[j],
527 points_j[(j + 1) % points_j.size()],
528 &alpha_a,
529 &alpha_b);
530 if (val == ISECT_LINE_LINE_CROSS || val == ISECT_LINE_LINE_EXACT) {
531 r_inters_per_curves[curve_i].append(r_intersections.size());
532 r_inters_per_curves[curve_j].append(r_intersections.size());
533 r_intersections.append(create_intersection(
534 i + point_offset_i, j + point_offset_j, alpha_a, alpha_b, curve_i, curve_j));
535 }
536 }
537 }
538}
539
540/* TODO: This method of finding intersections is O(N^2) and should replaced with something faster.
541 * This should be optimized with a BVH. */
543 const GroupedSpan<int> shapes,
544 const IndexMask &shapes_i,
545 const IndexMask &shapes_j,
546 const OffsetIndices<int> points_by_curve,
547 const VArray<bool> &cyclic,
548 const bool self_intersection,
549 Array<Vector<int>> &r_inters_per_curves,
550 Vector<IntersectionPoint> &r_intersections)
551{
552 shapes_i.foreach_index([&](const int shape_i) {
553 const Span<int> curves_i = shapes[shape_i];
554 for (const int curve_i : curves_i) {
555
556 const IndexRange points_i = points_by_curve[curve_i];
557 const bool cyclic_i = cyclic[curve_i];
558
559 shapes_j.foreach_index([&](const int shape_j) {
560 const Span<int> curves_j = shapes[shape_j];
561 for (const int curve_j : curves_j) {
562 if (self_intersection && curve_i >= curve_j) {
563 return;
564 }
565
566 const IndexRange points_j = points_by_curve[curve_j];
567 const bool cyclic_j = cyclic[curve_j];
568
570 points.slice(points_j),
571 curve_i,
572 curve_j,
573 cyclic_i,
574 cyclic_j,
575 points_i.first(),
576 points_j.first(),
577 r_inters_per_curves,
578 r_intersections);
579 }
580 });
581 }
582 });
583}
584
586 const Span<IntersectionPoint> &intersections,
587 const Span<bool> &segments_to_keep,
588 MutableSpan<SegmentConnections> segment_connections)
589{
590 auto connect = [&](const EncodedConnection point_1, const EncodedConnection point_2) {
591 segment_connections[decode_index(point_1)][decode_side(point_1)] = encode_index_and_side(
592 decode_index(point_2), decode_side(point_2));
593 segment_connections[decode_index(point_2)][decode_side(point_2)] = encode_index_and_side(
594 decode_index(point_1), decode_side(point_1));
595 };
596
597 for (const int inter_id : intersections.index_range()) {
598 const IntersectionPoint &inter = intersections[inter_id];
599
601 Side::End);
605 Side::End);
608 const bool is_start_a = start_a == SEGMENT_CONNECTION_NULL ?
609 false :
610 segments_to_keep[decode_index(start_a)];
611 const bool is_end_a = end_a == SEGMENT_CONNECTION_NULL ? false :
612 segments_to_keep[decode_index(end_a)];
613 const bool is_start_b = start_b == SEGMENT_CONNECTION_NULL ?
614 false :
615 segments_to_keep[decode_index(start_b)];
616 const bool is_end_b = end_b == SEGMENT_CONNECTION_NULL ? false :
617 segments_to_keep[decode_index(end_b)];
618
619 if (is_start_a && is_end_a && is_start_b && is_end_b) {
620 connect(start_a, end_a);
621 connect(start_b, end_b);
622 }
623 else if (is_start_a && is_end_a && is_start_b && !is_end_b) {
624 connect(start_a, end_a);
625 }
626 else if (is_start_a && is_end_a && !is_start_b && is_end_b) {
627 connect(start_a, end_a);
628 }
629 else if (is_start_a && is_end_a && !is_start_b && !is_end_b) {
630 connect(start_a, end_a);
631 }
632 else if (is_start_a && !is_end_a && is_start_b && is_end_b) {
633 connect(start_b, end_b);
634 }
635 else if (is_start_a && !is_end_a && is_start_b && !is_end_b) {
636 connect(start_a, start_b);
637 }
638 else if (is_start_a && !is_end_a && !is_start_b && is_end_b) {
639 connect(start_a, end_b);
640 }
641 else if (is_start_a && !is_end_a && !is_start_b && !is_end_b) {
642 /* Pass. */
643 }
644 else if (!is_start_a && is_end_a && is_start_b && is_end_b) {
645 connect(start_b, end_b);
646 }
647 else if (!is_start_a && is_end_a && is_start_b && !is_end_b) {
648 connect(end_a, start_b);
649 }
650 else if (!is_start_a && is_end_a && !is_start_b && is_end_b) {
651 connect(end_a, end_b);
652 }
653 else if (!is_start_a && is_end_a && !is_start_b && !is_end_b) {
654 /* Pass. */
655 }
656 else if (!is_start_a && !is_end_a && is_start_b && is_end_b) {
657 connect(start_b, end_b);
658 }
659 else if (!is_start_a && !is_end_a && is_start_b && !is_end_b) {
660 /* Pass. */
661 }
662 else if (!is_start_a && !is_end_a && !is_start_b && is_end_b) {
663 /* Pass. */
664 }
665 else if (!is_start_a && !is_end_a && !is_start_b && !is_end_b) {
666 /* Pass. */
667 }
668 }
669}
670
672 const int subj_shape_id,
673 const Span<float2> points,
674 const GroupedSpan<int> shapes,
675 const OffsetIndices<int> points_by_curve,
676 const IndexMask &clipping_shapes,
677 const VArray<bool> &is_fill,
678 const VArray<bool> &cyclic)
679{
680 Vector<IntersectionPoint> intersections;
681
682 Array<Vector<int>> inters_per_curves(points_by_curve.size());
683
684 const IndexMask subj_shapes = IndexRange::from_single(subj_shape_id);
685
687 shapes,
688 subj_shapes,
689 clipping_shapes,
690 points_by_curve,
691 cyclic,
692 false,
693 inters_per_curves,
694 intersections);
695
696 Vector<Segment> all_segments;
697 Array<int> all_segment_offset_data(points_by_curve.size() + 1, 0);
698
699 for (const int curve_i : shapes[subj_shape_id]) {
700 all_segment_offset_data[curve_i] = create_segments_from_intersections_single_curve(
701 curve_i, inters_per_curves, points_by_curve, intersections, cyclic, all_segments);
702 }
703
704 clipping_shapes.foreach_index([&](const int clip_shape_i) {
705 const Span<int> curves_j = shapes[clip_shape_i];
706 for (const int curve_j : curves_j) {
707 all_segment_offset_data[curve_j] = create_segments_from_intersections_single_curve(
708 curve_j, inters_per_curves, points_by_curve, intersections, cyclic, all_segments);
709 }
710 });
711
712 store_segment_map_on_intersections(all_segments, intersections);
714 all_segment_offset_data);
715
716 Array<bool> all_inside_left(all_segments.size());
717 Array<bool> all_inside_right(all_segments.size());
718
719 for (const int curve_i : shapes[subj_shape_id]) {
721 curve_i,
722 true,
723 subj_shape_id,
724 points,
725 shapes,
726 points_by_curve,
727 clipping_shapes,
728 all_segments,
729 segments_by_curve,
730 is_fill,
731 all_inside_left,
732 all_inside_right);
733 }
734 clipping_shapes.foreach_index([&](const int clip_shape_id) {
735 const Span<int> curves_j = shapes[clip_shape_id];
736 for (const int curve_j : curves_j) {
738 curve_j,
739 false,
740 subj_shape_id,
741 points,
742 shapes,
743 points_by_curve,
744 clipping_shapes,
745 all_segments,
746 segments_by_curve,
747 is_fill,
748 all_inside_left,
749 all_inside_right);
750 }
751 });
752
753 Array<bool> segments_to_keep(all_segments.size(), true);
754 for (const int segment_i : all_segments.index_range()) {
755 const Segment &segment = all_segments[segment_i];
756
757 if (is_fill[segment.curve]) {
758 if (!all_inside_left[segment_i] ^ all_inside_right[segment_i]) {
759 segments_to_keep[segment_i] = false;
760 }
761 }
762 else {
763 BLI_assert(all_inside_left[segment_i] == all_inside_right[segment_i]);
764 if (all_inside_left[segment_i]) {
765 segments_to_keep[segment_i] = false;
766 }
767 }
768 }
769
770 Array<SegmentConnections> segment_connections(all_segments.size(),
773 intersections, segments_to_keep, segment_connections);
774
776 follow_segment_connections(all_segments,
777 segments_to_keep,
778 segment_connections,
779 result.segments,
780 result.segment_offsets,
781 result.segment_reversed,
782 result.cyclic);
783
784 return result;
785}
786
788 const Span<bool> is_segments_clipping,
789 const OffsetIndices<int> segment_offsets)
790{
791 Array<bool> unchanged_curves(segment_offsets.size(), false);
792
793 for (const int dst_curve_i : segment_offsets.index_range()) {
794 const IndexRange segment_range = segment_offsets[dst_curve_i];
795 if (segment_range.size() != 1) {
796 continue;
797 }
798
799 const int segment_i = segment_range.first();
800 const Segment &segment = segments[segment_i];
801 if (segment.has_intersection(Side::Start) || segment.has_intersection(Side::End)) {
802 continue;
803 }
804
805 if (is_segments_clipping[segment_i]) {
806 continue;
807 }
808
809 unchanged_curves[dst_curve_i] = true;
810 }
811
812 return unchanged_curves;
813}
814
816 const Span<float2> positions_2d,
817 const OffsetIndices<int> points_by_curve,
818 const IndexMask &editable_shapes,
819 const IndexMask &clipping_shapes,
820 const GroupedSpan<int> shapes,
821 const VArray<int> &fill_ids,
822 const VArray<bool> &is_cyclic)
823{
824 BooleanResult results_all;
825 results_all.segment_offsets.append(0);
826
827 if (points_by_curve.is_empty()) {
828 return results_all;
829 }
830
831 IndexMaskMemory memory;
832 const IndexMask subject_shapes = clipping_shapes.complement(shapes.index_range(), memory);
833
834 /* Treat filled curves as cyclical. */
835 const VArray<bool> cyclic = VArray<bool>::from_func(points_by_curve.size(), [&](int64_t index) {
836 return is_cyclic[index] || (fill_ids[index] != 0);
837 });
838
839 const VArray<bool> is_fill = VArray<bool>::from_func(points_by_curve.size(), [&](int64_t index) {
840 const IndexRange points = points_by_curve[index];
841
842 if (points.size() <= 2) {
843 return false;
844 }
845
846 return fill_ids[index] != 0;
847 });
848
849 Array<Bounds<float2>> screen_space_bbox(shapes.size());
850 compute_bounding_boxes(points_by_curve, shapes, positions_2d, screen_space_bbox);
851
852 Array<bool> shapes_bbox_intersecting(shapes.size(), false);
853 index_mask::masked_fill(shapes_bbox_intersecting.as_mutable_span(), true, clipping_shapes);
854
855 /* Calculate which bounding boxes intersect the clipping shapes. */
856 subject_shapes.foreach_index([&](const int64_t shape_i) {
857 const Bounds<float2> bbox_i = screen_space_bbox[shape_i];
858
859 bool box_intersects = false;
860
861 clipping_shapes.foreach_index([&](const int64_t shape_j) {
862 const Bounds<float2> bbox_j = screen_space_bbox[shape_j];
863
864 if (bounds::intersect(bbox_i, bbox_j).has_value()) {
865 box_intersects = true;
866 }
867 });
868
869 if (box_intersects) {
870 shapes_bbox_intersecting[shape_i] = true;
871 }
872 });
873
874 Array<bool> editable_shapes_bool(shapes.size());
875 editable_shapes.to_bools(editable_shapes_bool);
876
877 subject_shapes.foreach_index([&](const int64_t shape_i) {
878 /* Only do full calculation with the bounding boxes are intersecting. */
879 if (shapes_bbox_intersecting[shape_i] && editable_shapes_bool[shape_i]) {
880 const BooleanResult result = execute_single_boolean(op_params,
881 shape_i,
882 positions_2d,
883 shapes,
884 points_by_curve,
885 clipping_shapes,
886 is_fill,
887 cyclic);
888
889 const int subj_first_curve = shapes[shape_i].first();
890 results_all.append_result(result, subj_first_curve);
891 }
892 else {
893 /* Don't add the shape when in intersect mode. */
894 if (op_params.boolean_mode == Operation::Intersect && !editable_shapes_bool[shape_i]) {
895 return;
896 }
897
898 BooleanResult result;
899 result.segment_offsets.append(0);
900
901 const Span<int> shape = shapes[shape_i];
902 for (const int pos_j : shape.index_range()) {
903 const int curve_j = shape[pos_j];
904
905 result.segments.append(
906 Segment::from_curve(curve_j, points_by_curve[curve_j], is_cyclic[curve_j]));
907 result.cyclic.append(is_cyclic[curve_j]);
908 result.segment_offsets.append(pos_j + 1);
909 result.segment_reversed.append(false);
910 }
911
912 const int subj_first_curve = shape.first();
913 results_all.append_result(result, subj_first_curve);
914 }
915 });
916
917 if (results_all.segments.is_empty()) {
918 return results_all;
919 }
920
921 const OffsetIndices<int> dst_segments_by_curve = OffsetIndices<int>(results_all.segment_offsets);
922
923 Array<bool> is_src_curve_clipping(points_by_curve.size(), false);
924 for (const int curve_i : points_by_curve.index_range()) {
925 if (curve_i == points_by_curve.index_range().last()) {
926 is_src_curve_clipping[curve_i] = true;
927 }
928 }
929
930 results_all.is_segments_clipping = Array<bool>(results_all.segments.size());
931 for (const int seg_i : results_all.segments.index_range()) {
932 const Segment &segment = results_all.segments[seg_i];
933 results_all.is_segments_clipping[seg_i] = is_src_curve_clipping[segment.curve];
934 }
935
936 results_all.dst_to_src_curves = Array<int>(dst_segments_by_curve.size());
937 for (const int i : dst_segments_by_curve.index_range()) {
938 const IndexRange segment_range = dst_segments_by_curve[i];
939 const int subj_first_curve = results_all.subj_first_curves[i];
940 results_all.dst_to_src_curves[i] = subj_first_curve;
941
942 /* Prioritize non-clipping curves. */
943 for (const int seg_i : segment_range) {
944 const int curve_i = results_all.segments[seg_i].curve;
945 if (!is_src_curve_clipping[curve_i]) {
946 results_all.dst_to_src_curves[i] = curve_i;
947 break;
948 }
949 }
950 }
951
952 results_all.unchanged_curves = calculate_unchanged_curves(
953 results_all.segments, results_all.is_segments_clipping, dst_segments_by_curve);
954
955 return results_all;
956}
957
959 const Span<Segment> segments,
960 const Span<bool> segment_reversed,
961 const Span<bool> cyclic,
962 const Span<bool> is_segments_clipping,
963 const Span<int> dst_to_src_curves,
964 const OffsetIndices<int> segment_offsets,
965 const Span<bool> unchanged_curves,
966 const bool skip_clipping_attributes,
967 Vector<bool> &r_is_point_clipping)
968{
969 IndexMaskMemory memory;
970 const IndexMask unchanged_curves_mask = IndexMask::from_bools(unchanged_curves, memory);
971
972 struct InterpolatePoint {
973 int dst_point;
974 int src_point_1;
975 int src_point_2;
976 float factor;
977 };
978
979 Array<int> point_offsets(segment_offsets.size() + 1);
980 Vector<int2> points_to_copy;
981 Vector<int2> clipping_points_to_copy;
982 Vector<IndexRange> ranges_to_reverse;
983 Vector<InterpolatePoint> point_to_interpolate;
984
985 int i = 0;
986 for (const int curve_i : segment_offsets.index_range()) {
987 point_offsets[curve_i] = i;
988
989 const bool unchanged = unchanged_curves[curve_i];
990
991 const IndexRange segment_range = segment_offsets[curve_i];
992 for (const int seg_i : segment_range) {
993 const Segment &segment = segments[seg_i];
994 const bool reversed = segment_reversed[seg_i];
995 const bool is_clipping = is_segments_clipping[seg_i];
996 const int point_num = segment.points_num();
997
998 if (segment.has_intersection(reversed ? Side::End : Side::Start) && !segment.is_loop()) {
999 const float start_alpha = segment.intersection_factor[reversed ? Side::End : Side::Start];
1000 const int2 start_edge = segment.edge(reversed ? Side::End : Side::Start);
1001 point_to_interpolate.append({i, start_edge.x, start_edge.y, start_alpha});
1002 r_is_point_clipping.append(is_clipping);
1003 i++;
1004 }
1005
1006 r_is_point_clipping.append_n_times(is_clipping, point_num);
1007
1008 if (!unchanged && !is_clipping) {
1009 segment.foreach_point(
1010 [&](const int index, const int pos) { points_to_copy.append(int2(pos + i, index)); });
1011
1012 if (reversed) {
1013 ranges_to_reverse.append(IndexRange::from_begin_size(i, point_num));
1014 }
1015 }
1016 if (is_clipping) {
1017 if (reversed) {
1018 segment.foreach_point([&](const int index, const int pos) {
1019 clipping_points_to_copy.append(int2(point_num - 1 - pos + i, index));
1020 });
1021 }
1022 else {
1023 segment.foreach_point([&](const int index, const int pos) {
1024 clipping_points_to_copy.append(int2(pos + i, index));
1025 });
1026 }
1027 }
1028
1029 i += point_num;
1030
1031 if (seg_i == segment_range.last() &&
1032 segment.has_intersection(reversed ? Side::Start : Side::End) && !cyclic[curve_i])
1033 {
1034 const float end_alpha = segment.intersection_factor[reversed ? Side::Start : Side::End];
1035 const int2 end_edge = segment.edge(reversed ? Side::Start : Side::End);
1036 point_to_interpolate.append({i, end_edge.x, end_edge.y, end_alpha});
1037 r_is_point_clipping.append(is_clipping);
1038 i++;
1039 }
1040 }
1041 }
1042 point_offsets.last() = i;
1043
1044 const OffsetIndices<int> dst_points_by_curve = OffsetIndices<int>(point_offsets);
1045
1046 const bke::AttributeAccessor src_attributes = src.attributes();
1047 const VArray<bool> src_cyclic = src.cyclic();
1048 const OffsetIndices<int> src_points_by_curve = src.points_by_curve();
1049 bke::CurvesGeometry dst_curves(dst_points_by_curve.total_size(), dst_points_by_curve.size());
1050 bke::MutableAttributeAccessor dst_attributes = dst_curves.attributes_for_write();
1051
1052 dst_curves.offsets_for_write().copy_from(dst_points_by_curve.data());
1053
1054 Vector<InterpolatePoint> clipping_point_to_interpolate;
1055 for (const int curve_i : dst_points_by_curve.index_range()) {
1056 const IndexRange points = dst_points_by_curve[curve_i];
1057 const Span<bool> range_is_clipping = r_is_point_clipping.as_span().slice(points);
1058
1059 const IndexMask clipping_ranges = IndexMask::from_bools(range_is_clipping, memory);
1060
1061 /* If the curve is entirely clipping, then take the point data from some point of the source
1062 * curve. */
1063 if (clipping_ranges == points.index_range()) {
1064 const int src_curve_i = dst_to_src_curves[curve_i];
1065 const IndexRange src_points = src_points_by_curve[src_curve_i];
1066
1067 /* Take the attribute data from the middle point of the source curve. */
1068 const int mid_point_index = int((src_points.first() + src_points.last()) / 2);
1069
1070 for (const int point_i : points) {
1071 clipping_point_to_interpolate.append(
1072 {int(point_i), mid_point_index, mid_point_index, 0.0f});
1073 }
1074 continue;
1075 }
1076
1077 clipping_ranges.foreach_range([&](const IndexRange &range) {
1078 const IndexRange full_range = range.shift(points.first());
1079 int range_first = int(full_range.first() - 1);
1080 int range_last = int(full_range.last() + 1);
1081 if (range_first == points.first() - 1) {
1082 range_first = points.last();
1083 }
1084 if (range_last == points.last() + 1) {
1085 range_last = points.first();
1086 }
1087 for (const int i : range.index_range()) {
1088 const float t = (i + 1.0f) / (range.size() + 1.0f);
1089 clipping_point_to_interpolate.append({int(full_range[i]), range_first, range_last, t});
1090 }
1091 });
1092 }
1093
1094 bke::gather_attributes(src_attributes,
1098 dst_to_src_curves,
1099 dst_attributes);
1100
1101 MutableSpan<bool> dst_cyclic = dst_curves.cyclic_for_write();
1102 dst_cyclic.copy_from(cyclic);
1103 unchanged_curves_mask.foreach_index(
1104 [&](const int i) { dst_cyclic[i] = src_cyclic[dst_to_src_curves[i]]; });
1105
1106 /* Copy/Interpolate point attributes. */
1108 src_attributes, dst_attributes, {bke::AttrDomain::Point}, {}))
1109 {
1110 bke::attribute_math::to_static_type(attribute.dst.span.type(), [&]<typename T>() {
1111 auto src_attr = attribute.src.typed<T>();
1112 auto dst_attr = attribute.dst.span.typed<T>();
1113
1114 for (const InterpolatePoint &interpolate_point : point_to_interpolate) {
1115 dst_attr[interpolate_point.dst_point] = bke::attribute_math::mix2<T>(
1116 interpolate_point.factor,
1117 src_attr[interpolate_point.src_point_1],
1118 src_attr[interpolate_point.src_point_2]);
1119 }
1120 for (const int2 index : points_to_copy) {
1121 dst_attr[index.x] = src_attr[index.y];
1122 }
1123 for (const int2 index : clipping_points_to_copy) {
1124 dst_attr[index.x] = src_attr[index.y];
1125 }
1126 for (const IndexRange range : ranges_to_reverse) {
1127 dst_attr.slice(range).reverse();
1128 }
1129 });
1130
1131 attribute.dst.finish();
1132 }
1133
1134 if (skip_clipping_attributes) {
1135 src_attributes.foreach_attribute([&](const bke::AttributeIter &iter) {
1136 if (iter.domain != bke::AttrDomain::Point) {
1137 return;
1138 }
1139 if (iter.data_type == bke::AttrType::String) {
1140 return;
1141 }
1142 const GVArraySpan src = *iter.get(bke::AttrDomain::Point);
1143 bke::GSpanAttributeWriter dst = dst_attributes.lookup_or_add_for_write_only_span(
1145 if (!dst) {
1146 return;
1147 }
1148 unchanged_curves_mask.foreach_index([&](const int i) {
1149 dst.span.slice(dst_points_by_curve[i])
1150 .copy_from(src.slice(src_points_by_curve[dst_to_src_curves[i]]));
1151 });
1152
1153 if (iter.name != "position") {
1154 GMutableSpan attribute_data = dst.span;
1155 bke::attribute_math::to_static_type(attribute_data.type(), [&]<typename T>() {
1156 MutableSpan<T> span_data = attribute_data.typed<T>();
1157
1158 for (const InterpolatePoint &interpolate_point : clipping_point_to_interpolate) {
1159 span_data[interpolate_point.dst_point] = bke::attribute_math::mix2<T>(
1160 interpolate_point.factor,
1161 span_data[interpolate_point.src_point_1],
1162 span_data[interpolate_point.src_point_2]);
1163 }
1164 });
1165 }
1166
1167 dst.finish();
1168 });
1169 }
1170
1171 return dst_curves;
1172}
1173
1174static float4 transform_plane(const float4x4 &mat, const float4 &plane)
1175{
1176 float3 normal = float3(plane);
1177 float3 point = -normal * plane.w;
1178
1179 normal = math::transform_direction(mat, normal);
1180 point = math::transform_point(mat, point);
1181
1182 return float4(normal, -math::dot(normal, point));
1183}
1184
1187 const ProjectionFunc project_fn,
1188 const GroupedSpan<int> shapes,
1189 const IndexMask &editable_shapes,
1190 const IndexMask &clipping_shapes)
1191{
1192 Array<float2> src_positions_2d(curves.points_num());
1193 const Span<float3> positions = curves.positions();
1194 for (const int i : curves.points_range()) {
1195 src_positions_2d[i] = project_fn(positions[i]);
1196 }
1197
1198 const VArray<int> fill_ids = *curves.attributes().lookup<int>("fill_id", bke::AttrDomain::Curve);
1199
1200 const BooleanResult result = execute_boolean(op_params,
1201 src_positions_2d,
1202 curves.points_by_curve(),
1203 editable_shapes,
1204 clipping_shapes,
1205 shapes,
1206 fill_ids,
1207 curves.cyclic());
1208
1209 if (result.segments.is_empty()) {
1210 return bke::CurvesGeometry();
1211 }
1212
1213 const OffsetIndices<int> dst_segments_by_curve = OffsetIndices<int>(result.segment_offsets);
1214
1215 Vector<bool> is_point_clipping;
1217 result.segments,
1218 result.segment_reversed,
1219 result.cyclic,
1220 result.is_segments_clipping,
1221 result.dst_to_src_curves,
1222 dst_segments_by_curve,
1223 result.unchanged_curves,
1224 op_params.skip_clipping_attributes,
1225 is_point_clipping);
1226
1227 if (!op_params.keep_caps) {
1228 cut_caps(dst_curves,
1229 result.segments,
1230 result.segment_reversed,
1231 result.cyclic,
1232 dst_segments_by_curve);
1233 }
1234
1235 if (op_params.separate_islands) {
1236 separate_fill_islands(dst_curves, result.unchanged_curves, project_fn);
1237 }
1238
1239 return dst_curves;
1240}
1241
1244 const ProjectionFunc project_fn,
1245 const GroupedSpan<int> shapes,
1246 const Span<float4> curve_planes,
1247 const IndexMask &editable_shapes,
1248 const IndexMask &clipping_shapes,
1249 const float4x4 &layer_to_world,
1250 const ARegion &region)
1251{
1252 Array<float2> src_positions_2d(curves.points_num());
1253 const Span<float3> src_positions = curves.positions();
1254 for (const int i : curves.points_range()) {
1255 src_positions_2d[i] = project_fn(src_positions[i]);
1256 }
1257
1258 const VArray<int> fill_ids = *curves.attributes().lookup<int>("fill_id", bke::AttrDomain::Curve);
1259
1260 const BooleanResult result = execute_boolean(op_params,
1261 src_positions_2d,
1262 curves.points_by_curve(),
1263 editable_shapes,
1264 clipping_shapes,
1265 shapes,
1266 fill_ids,
1267 curves.cyclic());
1268
1269 if (result.segments.is_empty()) {
1270 return bke::CurvesGeometry();
1271 }
1272
1273 const OffsetIndices<int> dst_segments_by_curve = OffsetIndices<int>(result.segment_offsets);
1274
1275 Vector<bool> is_point_clipping;
1277 result.segments,
1278 result.segment_reversed,
1279 result.cyclic,
1280 result.is_segments_clipping,
1281 result.dst_to_src_curves,
1282 dst_segments_by_curve,
1283 result.unchanged_curves,
1284 op_params.skip_clipping_attributes,
1285 is_point_clipping);
1286
1287 const OffsetIndices<int> points_by_curve = dst_curves.points_by_curve();
1288 MutableSpan<float3> positions = dst_curves.positions_for_write();
1289 const float4x4 world_to_layer = math::invert(layer_to_world);
1290 for (const int curve_i : dst_curves.curves_range()) {
1291 const int src_curve = result.dst_to_src_curves[curve_i];
1292 const float4 &plane = transform_plane(layer_to_world, curve_planes[src_curve]);
1293 const IndexRange points = points_by_curve[curve_i];
1294
1295 for (const int point_i : points) {
1296 if (is_point_clipping[point_i]) {
1297 const float2 positions_2d = project_fn(positions[point_i]);
1298 ED_view3d_win_to_3d_on_plane(&region, plane, positions_2d, false, positions[point_i]);
1299 positions[point_i] = math::transform_point(world_to_layer, positions[point_i]);
1300 }
1301 }
1302 }
1303
1304 if (!op_params.keep_caps) {
1305 cut_caps(dst_curves,
1306 result.segments,
1307 result.segment_reversed,
1308 result.cyclic,
1309 dst_segments_by_curve);
1310 }
1311
1312 if (op_params.separate_islands) {
1313 separate_fill_islands(dst_curves, result.unchanged_curves, project_fn);
1314 }
1315
1316 return dst_curves;
1317}
1318
1319} // namespace blender::ed::greasepencil::boolean
Low-level operations for curves.
#define ISECT_LINE_LINE_EXACT
#define ISECT_LINE_LINE_CROSS
#define BLI_assert_unreachable()
long long int int64_t
constexpr const T & first() const
Definition BLI_span.hh:319
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
const T & last(const int64_t n=0) const
Definition BLI_array.hh:307
void copy_from(GSpan values)
GMutableSpan slice(const int64_t start, int64_t size) const
GSpan slice(const int64_t start, int64_t size) const
static IndexMask from_bools(Span< bool > bools, LinearAllocator<> &memory)
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 bool is_empty() const
static constexpr IndexRange from_begin_size(const int64_t begin, const int64_t size)
static constexpr IndexRange from_single(const int64_t index)
constexpr IndexRange index_range() const
constexpr IndexRange drop_front(int64_t n) const
constexpr Span slice(int64_t start, int64_t size) const
Definition BLI_span.hh:141
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
static VArray from_func(const int64_t size, GetFunc get_func)
int64_t size() const
void append(const T &value)
IndexRange index_range() const
void extend(Span< T > array)
Span< T > as_span() const
void append_n_times(const T &value, const int64_t n)
GAttributeReader get() const
MutableSpan< float3 > positions_for_write()
VArray< bool > cyclic() const
AttributeAccessor attributes() const
Span< float3 > positions() const
IndexRange curves_range() const
MutableSpan< int > offsets_for_write()
IndexRange points_range() const
MutableSpan< bool > cyclic_for_write()
OffsetIndices< int > points_by_curve() const
MutableAttributeAccessor attributes_for_write()
GSpanAttributeWriter lookup_for_write_span(StringRef name)
bool is_contributing(const CurveBooleanOpParameters op_params, const GroupedSpan< int > &shapes, const int subject_shape, const IndexMask &clipping_shapes) const
void add_to_curve(const int curve_i, const int winding_i)
bool is_in_shape(const int shape_id, const GroupedSpan< int > &shapes) const
bool is_in_shapes(const IndexMask &shape_mask, const GroupedSpan< int > &shapes) const
void foreach_range(ForeachRangeFn auto &&fn) const
IndexMask slice(IndexRange range) const
void foreach_index(Fn &&fn, Mode mode=exec_mode::serial) const
IndexMask complement(const IndexMask &universe, LinearAllocator<> &memory) const
#define attribute(slot)
#define T
Segment< FEdge *, Vec3r > segment
void to_static_type(const CPPType &cpp_type, Fn &&fn)
int get_next_available_fill_id(Span< int > fill_ids)
auto attribute_filter_from_skip_ref(const Span< StringRef > skip)
Vector< AttributeTransferData > retrieve_attributes_for_transfer(const AttributeAccessor src_attributes, MutableAttributeAccessor dst_attributes, Span< AttrDomain > domains, const AttributeFilter &attribute_filter={})
void gather_attributes(AttributeAccessor src_attributes, AttrDomain src_domain, AttrDomain dst_domain, const AttributeFilter &attribute_filter, const IndexMask &selection, MutableAttributeAccessor dst_attributes)
std::optional< Bounds< T > > intersect(const Bounds< T > &a, const Bounds< T > &b)
static BooleanResult execute_boolean(const CurveBooleanOpParameters op_params, const Span< float2 > positions_2d, const OffsetIndices< int > points_by_curve, const IndexMask &editable_shapes, const IndexMask &clipping_shapes, const GroupedSpan< int > shapes, const VArray< int > &fill_ids, const VArray< bool > &is_cyclic)
static void separate_fill_islands(bke::CurvesGeometry &dst, const Span< bool > unchanged_curves, const ProjectionFunc project_fn)
static float point_in_tri_winding(const float2 pt, const float2 v1, const float2 v2, const float2 v3)
static void find_intersections_between_curves(const Span< float2 > points_i, const Span< float2 > points_j, const int curve_i, const int curve_j, const bool cyclic_i, const bool cyclic_j, const int point_offset_i, const int point_offset_j, Array< Vector< int > > &r_inters_per_curves, Vector< IntersectionPoint > &r_intersections)
FunctionRef< float2(const float3)> ProjectionFunc
static void find_intersections_between_shapes(const Span< float2 > points, const GroupedSpan< int > shapes, const IndexMask &shapes_i, const IndexMask &shapes_j, const OffsetIndices< int > points_by_curve, const VArray< bool > &cyclic, const bool self_intersection, Array< Vector< int > > &r_inters_per_curves, Vector< IntersectionPoint > &r_intersections)
static void create_connections_from_intersection_points(const Span< IntersectionPoint > &intersections, const Span< bool > &segments_to_keep, MutableSpan< SegmentConnections > segment_connections)
static std::pair< WindingState, WindingState > LR_states_from_segment(const Segment &segment, const Span< float2 > all_positions, const OffsetIndices< int > points_by_curve, const GroupedSpan< int > shapes, const IndexMask &mask_shapes, const VArray< bool > &is_fill)
static int point_in_polygon_winding_int(const float2 &point, const Span< float2 > poly)
static BooleanResult execute_single_boolean(const CurveBooleanOpParameters op_params, const int subj_shape_id, const Span< float2 > points, const GroupedSpan< int > shapes, const OffsetIndices< int > points_by_curve, const IndexMask &clipping_shapes, const VArray< bool > &is_fill, const VArray< bool > &cyclic)
static float4 transform_plane(const float4x4 &mat, const float4 &plane)
static bke::CurvesGeometry create_curves_from_segments(const bke::CurvesGeometry &src, const Span< Segment > segments, const Span< bool > segment_reversed, const Span< bool > cyclic, const Span< bool > is_segments_clipping, const Span< int > dst_to_src_curves, const OffsetIndices< int > segment_offsets, const Span< bool > unchanged_curves, const bool skip_clipping_attributes, Vector< bool > &r_is_point_clipping)
bke::CurvesGeometry curve_boolean_with_planes(const CurveBooleanOpParameters op_params, const bke::CurvesGeometry &curves, const ProjectionFunc project_fn, const GroupedSpan< int > shapes, const Span< float4 > curve_planes, const IndexMask &editable_shapes, const IndexMask &clipping_shapes, const float4x4 &layer_to_world, const ARegion &region)
static void get_inside_states_for_segments(const CurveBooleanOpParameters &op_params, const int curve_k, const bool is_subj, const int subj_shape_i, const Span< float2 > points, const GroupedSpan< int > shapes, const OffsetIndices< int > points_by_curve, const IndexMask &clipping_shapes, const Span< Segment > all_segments, const OffsetIndices< int > segments_by_curve, const VArray< bool > &is_fill, MutableSpan< bool > all_inside_left, MutableSpan< bool > all_inside_right)
static int intersect(const float2 &P1, const float2 &P2, const float2 &Q1, const float2 &Q2, float *r_alpha_P, float *r_alpha_Q)
static Array< bool > calculate_unchanged_curves(const Span< Segment > segments, const Span< bool > is_segments_clipping, const OffsetIndices< int > segment_offsets)
bke::CurvesGeometry curve_boolean(const CurveBooleanOpParameters op_params, const bke::CurvesGeometry &curves, const ProjectionFunc project_fn, const GroupedSpan< int > shapes, const IndexMask &editable_shapes, const IndexMask &clipping_shapes)
static int point_in_polygon_winding_twice(const float2 &point, const Span< float2 > poly)
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)
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 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)
VecBase< EncodedConnection, 2 > SegmentConnections
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)
void masked_fill(MutableSpan< T > data, const T &value, const IndexMask &mask)
T distance(const T &a, const T &b)
T dot(const QuaternionBase< T > &a, const QuaternionBase< T > &b)
T min(const T &a, const T &b)
CartesianBasis invert(const CartesianBasis &basis)
T interpolate(const T &a, const T &b, const FactorT &t)
MatBase< T, NumCol, NumRow > normalize(const MatBase< T, NumCol, NumRow > &a)
VecBase< T, 3 > transform_direction(const MatBase< T, 3, 3 > &mat, const VecBase< T, 3 > &direction)
VecBase< T, 3 > transform_point(const CartesianBasis &basis, const VecBase< T, 3 > &v)
OffsetIndices< int > accumulate_counts_to_offsets(MutableSpan< int > counts_to_offsets, int start_offset=0)
Value parallel_reduce(IndexRange range, int64_t grain_size, const Value &identity, const Function &function, const Reduction &reduction)
Definition BLI_task.hh:127
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
__int64 int64_t
Definition BKE_text.h:90
VecBase< double, 2 > double2
MatBase< float, 4, 4 > float4x4
VecBase< float, 4 > float4
VecBase< int32_t, 2 > int2
VecBase< float, 2 > float2
bool ED_view3d_win_to_3d_on_plane(const ARegion *region, const float plane[4], const float mval[2], bool do_clip, float r_out[3])
int isect_seg_seg_v2_lambda_mu_db(const double v1[2], const double v2[2], const double v3[2], const double v4[2], double *r_lambda, double *r_mu)
ATTR_WARN_UNUSED_RESULT const BMVert * v2
MINLINE float line_point_side_v2(const float l1[2], const float l2[2], const float pt[2]) ATTR_WARN_UNUSED_RESULT
VecBase< float, 3 > float3
void append_result(const BooleanResult &other_result, const int subj_first_curve)