Blender V5.3
index_mask_expression.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2024 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
17
18#include "BLI_array.hh"
20#include "BLI_bit_span_ops.hh"
23#include "BLI_stack.hh"
24#include "BLI_task.hh"
25
26#include "BLI_strict_flags.hh" /* IWYU pragma: keep */
27
28namespace blender::index_mask {
29
34
39 enum class Type {
44 Unknown,
46 Full,
49 };
53 const IndexMask *mask = nullptr;
54};
55
60
74
79
85 enum class Type {
87 Full,
91 Indices,
92 };
93
97 const IndexMask *copy_mask = nullptr;
100};
101
106enum class ExactEvalMode {
111 Indices,
119};
120
122{
123 std::ranges::sort(boundaries, [](const CourseBoundary &a, const CourseBoundary &b) {
124 return a.index < b.index;
125 });
126}
127
129{
130 std::ranges::sort(boundaries,
132 return a.index < b.index;
133 });
134}
135
137static constexpr int64_t segment_size_threshold = 32;
138
141 const int64_t prev_boundary_index,
142 const int64_t current_boundary_index,
144{
145 const int64_t size = current_boundary_index - prev_boundary_index;
146 if (prev_segment) {
147 if (prev_segment->type == CoarseSegment::Type::Full &&
148 prev_segment->bounds.one_after_last() == prev_boundary_index)
149 {
150 prev_segment->bounds = prev_segment->bounds.with_new_end(current_boundary_index);
151 return *prev_segment;
152 }
153 if (current_boundary_index - prev_segment->bounds.start() < max_segment_size) {
154 if (prev_segment->bounds.size() + size < segment_size_threshold) {
155 /* Extend the previous segment because it's so small and change it into an unknown one. */
156 prev_segment->bounds = prev_segment->bounds.with_new_end(current_boundary_index);
157 prev_segment->type = CoarseSegment::Type::Unknown;
158 return *prev_segment;
159 }
160 }
161 }
162 result.segments.append(
163 {CoarseSegment::Type::Full, IndexRange::from_begin_size(prev_boundary_index, size)});
164 return result.segments.last();
165}
166
169 const int64_t prev_boundary_index,
170 const int64_t current_boundary_index,
172{
173 if (prev_segment) {
174 if (prev_segment->bounds.start() + segment_size_threshold >= prev_boundary_index) {
175 /* The previous segment is very short, so extend it. */
176 prev_segment->type = CoarseSegment::Type::Unknown;
177 prev_segment->bounds = prev_segment->bounds.with_new_end(current_boundary_index);
178 return *prev_segment;
179 }
180 }
181 result.segments.append(
183 IndexRange::from_begin_end(prev_boundary_index, current_boundary_index)});
184 return result.segments.last();
185}
186
189 const int64_t prev_boundary_index,
190 const int64_t current_boundary_index,
191 const IndexMask &copy_from_mask,
193{
194 if (prev_segment) {
195 if (prev_segment->type == CoarseSegment::Type::Copy &&
196 prev_segment->bounds.one_after_last() == prev_boundary_index &&
197 prev_segment->mask == &copy_from_mask)
198 {
199 /* Can extend the previous copy segment. */
200 prev_segment->bounds = prev_segment->bounds.with_new_end(current_boundary_index);
201 return *prev_segment;
202 }
203 if (prev_segment->bounds.start() + segment_size_threshold >= current_boundary_index) {
204 /* The previous and this segment together are very short, so better merge them together. */
205 prev_segment->bounds = prev_segment->bounds.with_new_end(current_boundary_index);
206 prev_segment->type = CoarseSegment::Type::Unknown;
207 return *prev_segment;
208 }
209 }
210 result.segments.append({CoarseSegment::Type::Copy,
211 IndexRange::from_begin_end(prev_boundary_index, current_boundary_index),
212 &copy_from_mask});
213 return result.segments.last();
214}
215
216static void evaluate_coarse_union(const Span<CourseBoundary> boundaries, CoarseResult &r_result)
217{
218 if (boundaries.is_empty()) {
219 return;
220 }
221
222 CoarseResult &result = r_result;
223 CoarseSegment *prev_segment = nullptr;
224 Vector<const CoarseSegment *, 16> active_segments;
225 int64_t prev_boundary_index = boundaries[0].index;
226
227 for (const CourseBoundary &boundary : boundaries) {
228 if (prev_boundary_index < boundary.index) {
229 /* Compute some properties of the input segments that were active between the current and the
230 * previous boundary. */
231 bool has_full = false;
232 bool has_unknown = false;
233 bool copy_from_single_mask = true;
234 const IndexMask *copy_from_mask = nullptr;
235 for (const CoarseSegment *active_segment : active_segments) {
236 switch (active_segment->type) {
238 has_unknown = true;
239 break;
240 }
242 has_full = true;
243 break;
244 }
246 if (!ELEM(copy_from_mask, nullptr, active_segment->mask)) {
247 copy_from_single_mask = false;
248 }
249 copy_from_mask = active_segment->mask;
250 break;
251 }
252 }
253 }
254 /* Determine the resulting coarse segment type based on the properties computed above. */
255 if (has_full) {
256 prev_segment = &add_coarse_segment__full(
257 prev_segment, prev_boundary_index, boundary.index, result);
258 }
259 else if (has_unknown || !copy_from_single_mask) {
260 prev_segment = &add_coarse_segment__unknown(
261 prev_segment, prev_boundary_index, boundary.index, result);
262 }
263 else if (copy_from_mask != nullptr && copy_from_single_mask) {
264 prev_segment = &add_coarse_segment__copy(
265 prev_segment, prev_boundary_index, boundary.index, *copy_from_mask, result);
266 }
267
268 prev_boundary_index = boundary.index;
269 }
270
271 /* Update active segments. */
272 if (boundary.is_begin) {
273 active_segments.append(boundary.segment);
274 }
275 else {
276 active_segments.remove_first_occurrence_and_reorder(boundary.segment);
277 }
278 }
279}
280
282 const int64_t terms_num,
283 CoarseResult &r_result)
284{
285 if (boundaries.is_empty()) {
286 return;
287 }
288
289 CoarseResult &result = r_result;
290 CoarseSegment *prev_segment = nullptr;
291 Vector<const CoarseSegment *, 16> active_segments;
292 int64_t prev_boundary_index = boundaries[0].index;
293
294 for (const CourseBoundary &boundary : boundaries) {
295 if (prev_boundary_index < boundary.index) {
296 /* Only if one segment of each term is active, it's possible that the output contains
297 * anything. */
298 if (active_segments.size() == terms_num) {
299 /* Compute some properties of the input segments that were active between the current and
300 * previous boundary. */
301 int full_count = 0;
302 int unknown_count = 0;
303 int copy_count = 0;
304 bool copy_from_single_mask = true;
305 const IndexMask *copy_from_mask = nullptr;
306 for (const CoarseSegment *active_segment : active_segments) {
307 switch (active_segment->type) {
309 unknown_count++;
310 break;
311 }
313 full_count++;
314 break;
315 }
317 copy_count++;
318 if (!ELEM(copy_from_mask, nullptr, active_segment->mask)) {
319 copy_from_single_mask = false;
320 }
321 copy_from_mask = active_segment->mask;
322 break;
323 }
324 }
325 }
326 /* Determine the resulting coarse segment type based on the properties computed above. */
327 BLI_assert(full_count + unknown_count + copy_count == terms_num);
328 if (full_count == terms_num) {
329 prev_segment = &add_coarse_segment__full(
330 prev_segment, prev_boundary_index, boundary.index, result);
331 }
332 else if (unknown_count > 0 || copy_count < terms_num || !copy_from_single_mask) {
333 prev_segment = &add_coarse_segment__unknown(
334 prev_segment, prev_boundary_index, boundary.index, result);
335 }
336 else if (copy_count == terms_num && copy_from_single_mask) {
337 prev_segment = &add_coarse_segment__copy(
338 prev_segment, prev_boundary_index, boundary.index, *copy_from_mask, result);
339 }
340 }
341
342 prev_boundary_index = boundary.index;
343 }
344
345 /* Update active segments. */
346 if (boundary.is_begin) {
347 active_segments.append(boundary.segment);
348 }
349 else {
350 active_segments.remove_first_occurrence_and_reorder(boundary.segment);
351 }
352 }
353}
354
356 CoarseResult &r_result)
357{
358 if (boundaries.is_empty()) {
359 return;
360 }
361
362 CoarseResult &result = r_result;
363 CoarseSegment *prev_segment = nullptr;
364 Vector<const CoarseSegment *> active_main_segments;
365 Vector<const CoarseSegment *, 16> active_subtract_segments;
366 int64_t prev_boundary_index = boundaries[0].index;
367
368 for (const DifferenceCourseBoundary &boundary : boundaries) {
369 if (prev_boundary_index < boundary.index) {
370 /* There is only one main term, so at most one main segment can be active at once. */
371 BLI_assert(active_main_segments.size() <= 1);
372 if (active_main_segments.size() == 1) {
373 const CoarseSegment &active_main_segment = *active_main_segments[0];
374 /* Compute some properties of the input segments that were active between the current and
375 * the previous boundary. */
376 bool has_subtract_full = false;
377 bool has_subtract_same_mask = false;
378 for (const CoarseSegment *active_subtract_segment : active_subtract_segments) {
379 switch (active_subtract_segment->type) {
381 break;
382 }
384 has_subtract_full = true;
385 break;
386 }
388 if (active_main_segment.type == CoarseSegment::Type::Copy) {
389 if (active_main_segment.mask == active_subtract_segment->mask) {
390 has_subtract_same_mask = true;
391 }
392 }
393 break;
394 }
395 }
396 }
397 /* Determine the resulting coarse segment type based on the properties computed above. */
398 if (has_subtract_full) {
399 /* Do nothing, the resulting segment is empty for the current range. */
400 }
401 else {
402 switch (active_main_segment.type) {
404 prev_segment = &add_coarse_segment__unknown(
405 prev_segment, prev_boundary_index, boundary.index, result);
406 break;
407 }
409 if (active_subtract_segments.is_empty()) {
410 prev_segment = &add_coarse_segment__full(
411 prev_segment, prev_boundary_index, boundary.index, result);
412 }
413 else {
414 prev_segment = &add_coarse_segment__unknown(
415 prev_segment, prev_boundary_index, boundary.index, result);
416 }
417 break;
418 }
420 if (active_subtract_segments.is_empty()) {
421 prev_segment = &add_coarse_segment__copy(prev_segment,
422 prev_boundary_index,
423 boundary.index,
424 *active_main_segment.mask,
425 result);
426 }
427 else if (has_subtract_same_mask) {
428 /* Do nothing, subtracting a mask from itself results in an empty mask. */
429 }
430 else {
431 prev_segment = &add_coarse_segment__unknown(
432 prev_segment, prev_boundary_index, boundary.index, result);
433 }
434 break;
435 }
436 }
437 }
438 }
439
440 prev_boundary_index = boundary.index;
441 }
442
443 /* Update active segments. */
444 if (boundary.is_main) {
445 if (boundary.is_begin) {
446 active_main_segments.append(boundary.segment);
447 }
448 else {
449 active_main_segments.remove_first_occurrence_and_reorder(boundary.segment);
450 }
451 }
452 else {
453 if (boundary.is_begin) {
454 active_subtract_segments.append(boundary.segment);
455 }
456 else {
457 active_subtract_segments.remove_first_occurrence_and_reorder(boundary.segment);
458 }
459 }
460 }
461}
462
479static CoarseResult evaluate_coarse(const Expr &root_expression,
480 const Span<const Expr *> eval_order,
481 const std::optional<IndexRange> eval_bounds = std::nullopt)
482{
483 /* An expression result for each intermediate expression. */
485 root_expression.expression_array_size());
486
487 /* Process expressions in a pre-determined order. */
488 for (const Expr *expression : eval_order) {
489 CoarseResult &expr_result = expression_results[expression->index].emplace();
490 switch (expression->type) {
491 case Expr::Type::Atomic: {
492 const AtomicExpr &expr = expression->as_atomic();
493
495 if (eval_bounds.has_value()) {
496 mask = expr.mask->slice_content(*eval_bounds);
497 }
498 else {
499 mask = *expr.mask;
500 }
501
502 if (!mask.is_empty()) {
503 const IndexRange bounds = mask.bounds();
504 if (const std::optional<IndexRange> range = mask.to_range()) {
505 expr_result.segments.append({CoarseSegment::Type::Full, bounds});
506 }
507 else {
508 expr_result.segments.append({CoarseSegment::Type::Copy, bounds, expr.mask});
509 }
510 }
511 break;
512 }
513 case Expr::Type::Union: {
514 const UnionExpr &expr = expression->as_union();
516 for (const Expr *term : expr.terms) {
517 const CoarseResult &term_result = *expression_results[term->index];
518 for (const CoarseSegment &segment : term_result.segments) {
519 boundaries.append({segment.bounds.first(), true, &segment});
520 boundaries.append({segment.bounds.one_after_last(), false, &segment});
521 }
522 }
523 sort_course_boundaries(boundaries);
524 evaluate_coarse_union(boundaries, expr_result);
525 break;
526 }
528 const IntersectionExpr &expr = expression->as_intersection();
530 for (const Expr *term : expr.terms) {
531 const CoarseResult &term_result = *expression_results[term->index];
532 for (const CoarseSegment &segment : term_result.segments) {
533 boundaries.append({segment.bounds.first(), true, &segment});
534 boundaries.append({segment.bounds.one_after_last(), false, &segment});
535 }
536 }
537 sort_course_boundaries(boundaries);
538 evaluate_coarse_intersection(boundaries, expr.terms.size(), expr_result);
539 break;
540 }
542 const DifferenceExpr &expr = expression->as_difference();
544 const CoarseResult &main_term_result = *expression_results[expr.terms[0]->index];
545 for (const CoarseSegment &segment : main_term_result.segments) {
546 boundaries.append({{segment.bounds.first(), true, &segment}, true});
547 boundaries.append({{segment.bounds.one_after_last(), false, &segment}, true});
548 }
549 for (const Expr *term : expr.terms.as_span().drop_front(1)) {
550 const CoarseResult &term_result = *expression_results[term->index];
551 for (const CoarseSegment &segment : term_result.segments) {
552 boundaries.append({{segment.bounds.first(), true, &segment}, false});
553 boundaries.append({{segment.bounds.one_after_last(), false, &segment}, false});
554 }
555 }
556 sort_course_boundaries(boundaries);
557 evaluate_coarse_difference(boundaries, expr_result);
558 break;
559 }
560 }
561 }
562
563 CoarseResult &final_result = *expression_results[root_expression.index];
564 return std::move(final_result);
565}
566
568{
569 /* TODO: Could first count the number of set bits. */
571 bits::foreach_1_index(bits, [&](const int64_t i) {
572 BLI_assert(i < max_segment_size);
573 indices_vec.append_unchecked(int16_t(i));
574 });
575 return allocator.construct_array_copy<int16_t>(indices_vec);
576}
577
589static IndexMaskSegment evaluate_exact_with_bits(const Expr &root_expression,
590 LinearAllocator<> &allocator,
591 const IndexRange bounds,
592 const Span<const Expr *> eval_order)
593{
594 BLI_assert(bounds.size() <= max_segment_size);
595 const int64_t bounds_min = bounds.start();
596 const int expr_array_size = root_expression.expression_array_size();
597
598 /* Make bit span sizes a multiple of `BitsPerInt`. This allows the bit-wise operations to run a
599 * bit more efficiently, because only full integers are processed. */
600 const int64_t ints_in_bounds = ceil_division(bounds.size(), bits::BitsPerInt);
601 BitGroupVector<16 * 1024> expression_results(
602 expr_array_size, ints_in_bounds * bits::BitsPerInt, false);
603
604 for (const Expr *expression : eval_order) {
605 MutableBoundedBitSpan expr_result = expression_results[expression->index];
606 switch (expression->type) {
607 case Expr::Type::Atomic: {
608 const AtomicExpr &expr = expression->as_atomic();
609 const IndexMask mask = expr.mask->slice_content(bounds);
610 mask.to_bits(expr_result, -bounds_min);
611 break;
612 }
613 case Expr::Type::Union: {
614 for (const Expr *term : expression->terms) {
615 expr_result |= expression_results[term->index];
616 }
617 break;
618 }
620 bits::copy_from_or(expr_result, expression_results[expression->terms[0]->index]);
621 for (const Expr *term : expression->terms.as_span().drop_front(1)) {
622 expr_result &= expression_results[term->index];
623 }
624 break;
625 }
627 bits::copy_from_or(expr_result, expression_results[expression->terms[0]->index]);
628 for (const Expr *term : expression->terms.as_span().drop_front(1)) {
630 [](const bits::BitInt a, const bits::BitInt b) { return a & ~b; },
631 expr_result,
632 expression_results[term->index]);
633 }
634 break;
635 }
636 }
637 }
638 const BoundedBitSpan final_bits = expression_results[root_expression.index];
639 const Span<int16_t> indices = bits_to_indices(final_bits, allocator);
640 return IndexMaskSegment(bounds_min, indices);
641}
642
645 const int64_t bounds_min,
646 int16_t *r_values)
647{
648 if (segments.is_empty()) {
649 return {};
650 }
651 if (segments.size() == 1) {
652 return segments[0];
653 }
654 if (segments.size() == 2) {
655 const IndexMaskSegment a = segments[0].shift(-bounds_min);
656 const IndexMaskSegment b = segments[1].shift(-bounds_min);
657 const int64_t size = std::set_union(a.begin(), a.end(), b.begin(), b.end(), r_values) -
658 r_values;
659 return {bounds_min, {r_values, size}};
660 }
661
662 /* Sort input segments by their size, so that smaller segments are unioned first. This results in
663 * smaller intermediate arrays and thus less work overall. */
664 Vector<IndexMaskSegment> sorted_segments(segments);
665 std::ranges::sort(sorted_segments, [](const IndexMaskSegment &a, const IndexMaskSegment &b) {
666 return a.size() < b.size();
667 });
668
669 std::array<int16_t, max_segment_size> tmp_indices;
670 /* Can use r_values for temporary values because if it's large enough for the final result, it's
671 * also large enough for intermediate results. */
672 int16_t *buffer_a = r_values;
673 int16_t *buffer_b = tmp_indices.data();
674
675 if (sorted_segments.size() % 2 == 1) {
676 /* Swap buffers so that the result is in #r_values in the end. */
677 std::swap(buffer_a, buffer_b);
678 }
679
680 int64_t count = 0;
681 {
682 /* Initial union. */
683 const IndexMaskSegment a = sorted_segments[0].shift(-bounds_min);
684 const IndexMaskSegment b = sorted_segments[1].shift(-bounds_min);
685 int16_t *dst = buffer_a;
686 count = std::set_union(a.begin(), a.end(), b.begin(), b.end(), dst) - dst;
687 }
688
689 /* Union one input into the result at a time. In theory, one could write an algorithm that unions
690 * multiple sorted arrays at once, but that's more complex and it's not obvious that it would be
691 * faster in the end. */
692 for (const int64_t segment_i : sorted_segments.index_range().drop_front(2)) {
693 const int16_t *a = buffer_a;
694 const IndexMaskSegment b = sorted_segments[segment_i].shift(-bounds_min);
695 int16_t *dst = buffer_b;
696 count = std::set_union(a, a + count, b.begin(), b.end(), dst) - dst;
697 std::swap(buffer_a, buffer_b);
698 }
699 return {bounds_min, {r_values, count}};
700}
701
704 const int64_t bounds_min,
705 int16_t *r_values)
706{
707 if (segments.is_empty()) {
708 return {};
709 }
710 if (segments.size() == 1) {
711 return segments[0];
712 }
713 if (segments.size() == 2) {
714 const IndexMaskSegment a = segments[0].shift(-bounds_min);
715 const IndexMaskSegment b = segments[1].shift(-bounds_min);
716 const int64_t size = std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), r_values) -
717 r_values;
718 return {bounds_min, {r_values, size}};
719 }
720
721 /* Intersect smaller segments first, because then the intermediate results will generally be
722 * smaller. */
723 Vector<IndexMaskSegment> sorted_segments(segments);
724 std::ranges::sort(sorted_segments, [](const IndexMaskSegment &a, const IndexMaskSegment &b) {
725 return a.size() < b.size();
726 });
727
728 std::array<int16_t, max_segment_size> tmp_indices_1;
729 std::array<int16_t, max_segment_size> tmp_indices_2;
730 int16_t *buffer_a = tmp_indices_1.data();
731 int16_t *buffer_b = tmp_indices_2.data();
732
733 int64_t count = 0;
734 {
735 /* Initial intersection. */
736 const IndexMaskSegment a = sorted_segments[0].shift(-bounds_min);
737 const IndexMaskSegment b = sorted_segments[1].shift(-bounds_min);
738 int16_t *dst = buffer_a;
739 count = std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), dst) - dst;
740 }
741
742 for (const int64_t segment_i : sorted_segments.index_range().drop_front(2)) {
743 const int16_t *a = buffer_a;
744 const IndexMaskSegment b = sorted_segments[segment_i].shift(-bounds_min);
745 /* The result of the final intersection should be written directly to #r_values to avoid an
746 * additional copy in the end. */
747 int16_t *dst = (segment_i == sorted_segments.size() - 1) ? r_values : buffer_b;
748 count = std::set_intersection(a, a + count, b.begin(), b.end(), dst) - dst;
749 std::swap(buffer_a, buffer_b);
750 }
751 return {bounds_min, {r_values, count}};
752}
753
759 const IndexMaskSegment main_segment,
760 const Span<IndexMaskSegment> subtract_segments,
761 const int64_t bounds_min,
762 int16_t *r_values)
763{
764 if (main_segment.is_empty()) {
765 return {};
766 }
767 if (subtract_segments.is_empty()) {
768 return main_segment;
769 }
770 if (subtract_segments.size() == 1) {
771 const IndexMaskSegment shifted_main_segment = main_segment.shift(-bounds_min);
772 const IndexMaskSegment subtract_segment = subtract_segments[0].shift(-bounds_min);
773 const int64_t size = std::set_difference(shifted_main_segment.begin(),
774 shifted_main_segment.end(),
775 subtract_segment.begin(),
776 subtract_segment.end(),
777 r_values) -
778 r_values;
779 return {bounds_min, {r_values, size}};
780 }
781
782 int64_t subtract_count = 0;
783 for (const IndexMaskSegment &segment : subtract_segments) {
784 subtract_count += segment.size();
785 }
786 if (subtract_count < main_segment.size() / 2) {
787 /* Can be more efficient to union all the subtract indices first before computing the
788 * difference. This avoids potentially multiple larger intermediate arrays. */
789 std::array<int16_t, max_segment_size> union_indices;
790 const IndexMaskSegment shifted_main_segment = main_segment.shift(-bounds_min);
791 const IndexMaskSegment unioned_subtract_segment =
792 union_index_mask_segments(subtract_segments, bounds_min, union_indices.data())
793 .shift(-bounds_min);
794 const int64_t size = std::set_difference(shifted_main_segment.begin(),
795 shifted_main_segment.end(),
796 unioned_subtract_segment.begin(),
797 unioned_subtract_segment.end(),
798 r_values) -
799 r_values;
800 return {bounds_min, {r_values, size}};
801 }
802
803 /* Sort larger segments to the front. This way the intermediate arrays are likely smaller. */
804 Vector<IndexMaskSegment> sorted_subtract_segments(subtract_segments);
805 std::ranges::sort(
806 sorted_subtract_segments,
807 [](const IndexMaskSegment &a, const IndexMaskSegment &b) { return a.size() > b.size(); });
808
809 std::array<int16_t, max_segment_size> tmp_indices_1;
810 std::array<int16_t, max_segment_size> tmp_indices_2;
811 int16_t *buffer_a = tmp_indices_1.data();
812 int16_t *buffer_b = tmp_indices_2.data();
813
814 int64_t count = 0;
815 {
816 /* Initial difference. */
817 const IndexMaskSegment shifted_main_segment = main_segment.shift(-bounds_min);
818 const IndexMaskSegment subtract_segment = sorted_subtract_segments[0].shift(-bounds_min);
819 int16_t *dst = buffer_a;
820 count = std::set_difference(shifted_main_segment.begin(),
821 shifted_main_segment.end(),
822 subtract_segment.begin(),
823 subtract_segment.end(),
824 dst) -
825 dst;
826 }
827
828 for (const int64_t segment_i : sorted_subtract_segments.index_range().drop_front(1)) {
829 const IndexMaskSegment &subtract_segment = sorted_subtract_segments[segment_i].shift(
830 -bounds_min);
831 /* The final result should be written directly to #r_values to avoid an additional copy. */
832 int16_t *dst = (segment_i == sorted_subtract_segments.size() - 1) ? r_values : buffer_b;
833 count = std::set_difference(buffer_a,
834 buffer_a + count,
835 subtract_segment.begin(),
836 subtract_segment.end(),
837 dst) -
838 dst;
839 std::swap(buffer_a, buffer_b);
840 }
841 return {bounds_min, {r_values, count}};
842}
843
850 LinearAllocator<> &allocator,
851 const IndexRange bounds,
852 const Span<const Expr *> eval_order)
853{
854 BLI_assert(bounds.size() <= max_segment_size);
855 const int64_t bounds_min = bounds.start();
856 const int expr_array_size = root_expression.expression_array_size();
858 for (const Expr *expression : eval_order) {
859 switch (expression->type) {
860 case Expr::Type::Atomic: {
861 const AtomicExpr &expr = expression->as_atomic();
862 const IndexMask mask = expr.mask->slice_content(bounds);
863 /* The caller should make sure that the bounds are aligned to segment bounds. */
864 BLI_assert(mask.segments_num() <= 1);
865 if (mask.segments_num() == 1) {
866 results[expression->index] = mask.segment(0);
867 }
868 break;
869 }
870 case Expr::Type::Union: {
871 const UnionExpr &expr = expression->as_union();
872 Array<IndexMaskSegment> term_segments(expr.terms.size());
873 int64_t result_size_upper_bound = 0;
874 bool used_short_circuit = false;
875 for (const int64_t term_i : expr.terms.index_range()) {
876 const Expr &term = *expr.terms[term_i];
877 const IndexMaskSegment term_segment = results[term.index];
878 if (term_segment.size() == bounds.size()) {
879 /* Can skip computing the union if we know that one of the inputs contains all possible
880 * indices already. */
881 results[expression->index] = term_segment;
882 used_short_circuit = true;
883 break;
884 }
885 term_segments[term_i] = term_segment;
886 result_size_upper_bound += term_segment.size();
887 }
888 if (used_short_circuit) {
889 break;
890 }
891 result_size_upper_bound = std::min(result_size_upper_bound, bounds.size());
892 MutableSpan<int16_t> dst = allocator.allocate_array<int16_t>(result_size_upper_bound);
893 const IndexMaskSegment result_segment = union_index_mask_segments(
894 term_segments, bounds_min, dst.data());
896 result_segment.base_span().end());
897 results[expression->index] = result_segment;
898 break;
899 }
901 const IntersectionExpr &expr = expression->as_intersection();
902 Array<IndexMaskSegment> term_segments(expr.terms.size());
903 int64_t result_size_upper_bound = bounds.size();
904 bool used_short_circuit = false;
905 for (const int64_t term_i : expr.terms.index_range()) {
906 const Expr &term = *expr.terms[term_i];
907 const IndexMaskSegment term_segment = results[term.index];
908 if (term_segment.is_empty()) {
909 /* Can skip computing the intersection if we know that one of the inputs is empty. */
910 results[expression->index] = {};
911 used_short_circuit = true;
912 break;
913 }
914 result_size_upper_bound = std::min(result_size_upper_bound, term_segment.size());
915 term_segments[term_i] = term_segment;
916 }
917 if (used_short_circuit) {
918 break;
919 }
920 MutableSpan<int16_t> dst = allocator.allocate_array<int16_t>(result_size_upper_bound);
921 const IndexMaskSegment result_segment = intersect_index_mask_segments(
922 term_segments, bounds_min, dst.data());
924 result_segment.base_span().end());
925 results[expression->index] = result_segment;
926 break;
927 }
929 const DifferenceExpr &expr = expression->as_difference();
930 const Expr &main_term = *expr.terms[0];
931 const IndexMaskSegment main_segment = results[main_term.index];
932 if (main_segment.is_empty()) {
933 /* Can skip the computation of the main segment is empty. */
934 results[expression->index] = {};
935 break;
936 }
937 int64_t result_size_upper_bound = main_segment.size();
938 bool used_short_circuit = false;
939 Array<IndexMaskSegment> subtract_segments(expr.terms.size() - 1);
940 for (const int64_t term_i : expr.terms.index_range().drop_front(1)) {
941 const Expr &subtract_term = *expr.terms[term_i];
942 const IndexMaskSegment term_segment = results[subtract_term.index];
943 if (term_segment.size() == bounds.size()) {
944 /* Can skip computing the difference if we know that one of the subtract-terms is
945 * full. */
946 results[expression->index] = {};
947 used_short_circuit = true;
948 break;
949 }
950 result_size_upper_bound = std::min(result_size_upper_bound,
951 bounds.size() - term_segment.size());
952 subtract_segments[term_i - 1] = term_segment;
953 }
954 if (used_short_circuit) {
955 break;
956 }
957 MutableSpan<int16_t> dst = allocator.allocate_array<int16_t>(result_size_upper_bound);
959 main_segment, subtract_segments, bounds_min, dst.data());
961 result_segment.base_span().end());
962 results[expression->index] = result_segment;
963 break;
964 }
965 }
966 }
967 return results[root_expression.index];
968}
969
975 const Span<EvaluatedSegment> evaluated_segments)
976{
977 Vector<IndexMaskSegment> result_mask_segments;
978 for (const EvaluatedSegment &evaluated_segment : evaluated_segments) {
979 switch (evaluated_segment.type) {
981 index_range_to_mask_segments(evaluated_segment.bounds, result_mask_segments);
982 break;
983 }
985 const IndexMask sliced_mask = evaluated_segment.copy_mask->slice_content(
986 evaluated_segment.bounds);
987 sliced_mask.foreach_segment(
988 [&](const IndexMaskSegment &segment) { result_mask_segments.append(segment); });
989 break;
990 }
992 result_mask_segments.append(evaluated_segment.indices);
993 break;
994 }
995 }
996 }
997 return result_mask_segments;
998}
999
1005{
1007 if (root_expression.type == Expr::Type::Atomic) {
1008 eval_order.append(&root_expression);
1009 return eval_order;
1010 }
1011
1012 Array<bool, inline_expr_array_size> is_evaluated_states(root_expression.expression_array_size(),
1013 false);
1015 expr_stack.push(&root_expression);
1016
1017 while (!expr_stack.is_empty()) {
1018 const Expr &expression = *expr_stack.peek();
1019 bool &is_evaluated = is_evaluated_states[expression.index];
1020 if (is_evaluated) {
1021 expr_stack.pop();
1022 continue;
1023 }
1024 bool all_terms_evaluated = true;
1025 for (const Expr *term : expression.terms) {
1026 bool &term_evaluated = is_evaluated_states[term->index];
1027 if (!term_evaluated) {
1028 if (term->type == Expr::Type::Atomic) {
1029 eval_order.append(term);
1030 term_evaluated = true;
1031 }
1032 else {
1033 expr_stack.push(term);
1034 all_terms_evaluated = false;
1035 }
1036 }
1037 }
1038 if (all_terms_evaluated) {
1039 eval_order.append(&expression);
1040 is_evaluated = true;
1041 expr_stack.pop();
1042 }
1043 }
1044
1045 return eval_order;
1046}
1047
1049static ExactEvalMode determine_exact_eval_mode(const Expr &root_expression)
1050{
1051 for (const Expr *term : root_expression.terms) {
1052 if (!term->terms.is_empty()) {
1053 /* Use bits when there are nested expressions as this is often faster. */
1054 return ExactEvalMode::Bits;
1055 }
1056 }
1058}
1059
1061 const Expr &root_expression,
1062 const Span<const Expr *> eval_order,
1063 Vector<EvaluatedSegment, 16> &r_evaluated_segments,
1064 Vector<IndexRange, 16> &r_short_unknown_segments)
1065{
1066 /* Coarse evaluation splits the full range into segments. Long segments are split up and get
1067 * another coarse evaluation. Short segments will be evaluated exactly. */
1068 Stack<IndexRange, 16> long_unknown_segments;
1069
1070 /* The point at which a range starts being "short". */
1071 const int64_t coarse_segment_size_threshold = max_segment_size;
1072
1073 /* Checks the coarse results and inserts its segments into either `long_unknown_segments` for
1074 * further coarse evaluation, `r_short_unknown_segments` for exact evaluation or
1075 * `r_evaluated_segments` if no further evaluation is necessary. */
1076 auto handle_coarse_result = [&](const CoarseResult &coarse_result) {
1077 for (const CoarseSegment &segment : coarse_result.segments) {
1078 switch (segment.type) {
1080 if (segment.bounds.size() > coarse_segment_size_threshold) {
1081 long_unknown_segments.push(segment.bounds);
1082 }
1083 else {
1084 r_short_unknown_segments.append(segment.bounds);
1085 }
1086 break;
1087 }
1089 BLI_assert(segment.mask);
1090 r_evaluated_segments.append(
1091 {EvaluatedSegment::Type::Copy, segment.bounds, segment.mask});
1092 break;
1093 }
1095 r_evaluated_segments.append({EvaluatedSegment::Type::Full, segment.bounds});
1096 break;
1097 }
1098 }
1099 }
1100 };
1101
1102 /* Initial coarse evaluation without any explicit bounds. The bounds are implied by the index
1103 * masks used in the expression. */
1104 const CoarseResult initial_coarse_result = evaluate_coarse(root_expression, eval_order);
1105 handle_coarse_result(initial_coarse_result);
1106
1107 /* Do coarse evaluation until all unknown segments are short enough to do exact evaluation. */
1108 while (!long_unknown_segments.is_empty()) {
1109 const IndexRange unknown_bounds = long_unknown_segments.pop();
1110 const int64_t split_pos = unknown_bounds.size() / 2;
1111 const IndexRange left_half = unknown_bounds.take_front(split_pos);
1112 const IndexRange right_half = unknown_bounds.drop_front(split_pos);
1113 const CoarseResult left_result = evaluate_coarse(root_expression, eval_order, left_half);
1114 const CoarseResult right_result = evaluate_coarse(root_expression, eval_order, right_half);
1115 handle_coarse_result(left_result);
1116 handle_coarse_result(right_result);
1117 }
1118}
1119
1121 const Expr &root_expression,
1122 const ExactEvalMode exact_eval_mode,
1123 const Span<const Expr *> eval_order,
1124 const Span<IndexRange> short_unknown_segments,
1125 LinearAllocator<> &memory,
1126 Vector<EvaluatedSegment, 16> &r_evaluated_segments)
1127{
1128 /* Evaluate a segment exactly. */
1129 auto evaluate_unknown_segment = [&](const IndexRange bounds,
1130 LinearAllocator<> &allocator,
1131 Vector<EvaluatedSegment, 16> &r_local_evaluated_segments) {
1132 /* Use the predetermined evaluation mode. */
1133 switch (exact_eval_mode) {
1134 case ExactEvalMode::Bits: {
1136 root_expression, allocator, bounds, eval_order);
1137 if (!indices.is_empty()) {
1138 r_local_evaluated_segments.append(
1139 {EvaluatedSegment::Type::Indices, bounds, nullptr, indices});
1140 }
1141 break;
1142 }
1144 /* #evaluate_exact_with_indices requires that all index masks have a single segment in the
1145 * provided bounds. So split up the range into sub-ranges first if necessary. */
1146 Vector<int64_t, 16> split_indices;
1147 /* Always adding the beginning and end of the bounds simplifies the code below. */
1148 split_indices.extend({bounds.first(), bounds.one_after_last()});
1149 for (const int64_t eval_order_i : eval_order.index_range()) {
1150 const Expr &expr = *eval_order[eval_order_i];
1151 if (expr.type != Expr::Type::Atomic) {
1152 continue;
1153 }
1154 const AtomicExpr &atomic_expr = expr.as_atomic();
1155 const IndexMask mask = atomic_expr.mask->slice_content(bounds);
1156 const int64_t segments_num = mask.segments_num();
1157 if (segments_num <= 1) {
1158 /* This mask only has a single segment in the bounds anyway, so no extra split-position
1159 * is necessary. */
1160 continue;
1161 }
1162 /* Split at the beginning of each segment. Skipping the first, because that does not need
1163 * an extra split position. Alternatively, one could also split at the end of each
1164 * segment except the last one. It doesn't matter much. */
1165 for (const int64_t segment_i : IndexRange(segments_num).drop_front(1)) {
1166 const IndexMaskSegment segment = mask.segment(segment_i);
1167 split_indices.append(segment[0]);
1168 }
1169 }
1170 std::ranges::sort(split_indices);
1171 for (const int64_t boundary_i : split_indices.index_range().drop_back(1)) {
1172 const IndexRange sub_bounds = IndexRange::from_begin_end(split_indices[boundary_i],
1173 split_indices[boundary_i + 1]);
1174 if (sub_bounds.is_empty()) {
1175 continue;
1176 }
1178 root_expression, allocator, sub_bounds, eval_order);
1179 if (!indices.is_empty()) {
1180 r_local_evaluated_segments.append(
1181 {EvaluatedSegment::Type::Indices, sub_bounds, nullptr, indices});
1182 }
1183 }
1184 break;
1185 }
1186 }
1187 };
1188
1189 /* Decide whether multi-threading should be used or not. There is some extra overhead even when
1190 * just attempting to use multi-threading. */
1191 const int64_t unknown_segment_eval_grain_size = 8;
1192 if (short_unknown_segments.size() < unknown_segment_eval_grain_size) {
1193 for (const IndexRange &bounds : short_unknown_segments) {
1194 evaluate_unknown_segment(bounds, memory, r_evaluated_segments);
1195 }
1196 }
1197 else {
1198 /* Do exact evaluation in multiple threads. The allocators and evaluated segments created by
1199 * each thread are merged in the end. */
1200 struct LocalData {
1201 LinearAllocator<> allocator;
1202 Vector<EvaluatedSegment, 16> evaluated_segments;
1203 };
1206 short_unknown_segments.index_range(),
1207 unknown_segment_eval_grain_size,
1208 [&](const IndexRange range) {
1209 LocalData &data = data_by_thread.local();
1210 for (const IndexRange &bounds : short_unknown_segments.slice(range)) {
1211 evaluate_unknown_segment(bounds, data.allocator, data.evaluated_segments);
1212 }
1213 });
1214 for (LocalData &data : data_by_thread) {
1215 if (!data.evaluated_segments.is_empty()) {
1216 r_evaluated_segments.extend(data.evaluated_segments);
1217 memory.transfer_ownership_from(data.allocator);
1218 }
1219 }
1220 }
1221}
1222
1224 LinearAllocator<> &memory)
1225{
1226 if (evaluated_segments.is_empty()) {
1227 return {};
1228 }
1229 if (evaluated_segments.size() == 1) {
1230 const EvaluatedSegment &evaluated_segment = evaluated_segments[0];
1231 switch (evaluated_segment.type) {
1233 return IndexMask(IndexRange(evaluated_segment.bounds));
1234 }
1236 return evaluated_segment.copy_mask->slice_content(evaluated_segment.bounds);
1237 }
1239 return IndexMask::from_segments({evaluated_segment.indices}, memory);
1240 }
1241 }
1242 }
1243
1244 std::ranges::sort(evaluated_segments, [](const EvaluatedSegment &a, const EvaluatedSegment &b) {
1245 return a.bounds.start() < b.bounds.start();
1246 });
1247
1248 Vector<IndexMaskSegment> result_segments = build_result_mask_segments(evaluated_segments);
1249 return IndexMask::from_segments(result_segments, memory);
1250}
1251
1252static IndexMask evaluate_expression_impl(const Expr &root_expression,
1253 LinearAllocator<> &memory,
1254 const ExactEvalMode exact_eval_mode)
1255{
1256 /* Precompute the evaluation order here, because it's used potentially many times throughout the
1257 * algorithm. */
1259 root_expression);
1260
1261 /* Non-overlapping evaluated segments which become the resulting index mask in the end. Note that
1262 * these segments are only sorted in the end. */
1263 Vector<EvaluatedSegment, 16> evaluated_segments;
1264 Vector<IndexRange, 16> short_unknown_segments;
1265
1267 root_expression, eval_order, evaluated_segments, short_unknown_segments);
1269 exact_eval_mode,
1270 eval_order,
1271 short_unknown_segments,
1272 memory,
1273 evaluated_segments);
1274 return evaluated_segments_to_index_mask(evaluated_segments, memory);
1275}
1276
1278{
1279 const ExactEvalMode exact_eval_mode = determine_exact_eval_mode(expression);
1280 IndexMask mask = evaluate_expression_impl(expression, memory, exact_eval_mode);
1281#ifndef NDEBUG
1282 {
1283 /* Check that both exact eval modes have the same result. */
1284 const ExactEvalMode other_exact_eval_mode = (exact_eval_mode == ExactEvalMode::Bits) ?
1287 IndexMask other_mask = evaluate_expression_impl(expression, memory, other_exact_eval_mode);
1288 BLI_assert(mask == other_mask);
1289 }
1290#endif
1291 return mask;
1292}
1293
1295{
1296 Vector<const Expr *> term_expressions;
1297 for (const Term &term : terms) {
1298 term_expressions.append(&this->term_to_expr(term));
1299 }
1300 UnionExpr &expr = scope_.construct<UnionExpr>();
1301 expr.type = Expr::Type::Union;
1302 expr.index = expr_count_++;
1303 expr.terms = std::move(term_expressions);
1304 return expr;
1305}
1306
1307const DifferenceExpr &ExprBuilder::subtract(const Term &main_term, const Span<Term> subtract_terms)
1308{
1309 Vector<const Expr *> term_expressions;
1310 term_expressions.append(&this->term_to_expr(main_term));
1311 for (const Term &subtract_term : subtract_terms) {
1312 term_expressions.append(&this->term_to_expr(subtract_term));
1313 }
1314 DifferenceExpr &expr = scope_.construct<DifferenceExpr>();
1316 expr.index = expr_count_++;
1317 expr.terms = std::move(term_expressions);
1318 return expr;
1319}
1320
1322{
1323 Vector<const Expr *> term_expressions;
1324 for (const Term &term : terms) {
1325 term_expressions.append(&this->term_to_expr(term));
1326 }
1327 IntersectionExpr &expr = scope_.construct<IntersectionExpr>();
1329 expr.index += expr_count_++;
1330 expr.terms = std::move(term_expressions);
1331 return expr;
1332}
1333
1334const Expr &ExprBuilder::term_to_expr(const Term &term)
1335{
1336 if (const Expr *const *expr = std::get_if<const Expr *>(&term)) {
1337 return **expr;
1338 }
1339 AtomicExpr &expr = scope_.construct<AtomicExpr>();
1340 expr.type = Expr::Type::Atomic;
1341 expr.index = expr_count_++;
1342 if (const IndexRange *range = std::get_if<IndexRange>(&term)) {
1343 expr.mask = &scope_.construct<IndexMask>(*range);
1344 }
1345 else {
1346 expr.mask = std::get<const IndexMask *>(term);
1347 }
1348 return expr;
1349}
1350
1351} // namespace blender::index_mask
#define ELEM(...)
constexpr int64_t one_after_last() const
constexpr IndexRange drop_back(int64_t n) const
constexpr int64_t size() const
constexpr bool is_empty() const
static constexpr IndexRange from_begin_end(const int64_t begin, const int64_t end)
constexpr IndexRange with_new_end(const int64_t new_end) const
constexpr IndexRange()=default
static constexpr IndexRange from_begin_size(const int64_t begin, const int64_t size)
constexpr int64_t start() const
constexpr IndexRange take_front(int64_t n) const
constexpr IndexRange drop_front(int64_t n) const
MutableSpan< T > allocate_array(int64_t size)
void free_end_of_previous_allocation(const int64_t original_allocation_size, const void *free_after)
MutableSpan< T > construct_array_copy(Span< T > src)
void transfer_ownership_from(LinearAllocator<> &other)
constexpr int64_t size() const
Definition BLI_span.hh:499
constexpr bool is_empty() const
Definition BLI_span.hh:515
constexpr T * data() const
Definition BLI_span.hh:545
constexpr int64_t size_in_bytes() const
Definition BLI_span.hh:507
Iterator begin() const
int64_t size() const
Iterator end() const
constexpr const T * data() const
Definition BLI_span.hh:219
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 remove_first_occurrence_and_reorder(const T &value)
IndexRange index_range() const
void append_unchecked(const T &value)
void extend(Span< T > array)
std::variant< const Expr *, const IndexMask *, IndexRange > Term
const IntersectionExpr & intersect(const Span< Term > terms)
const UnionExpr & merge(const Span< Term > terms)
const DifferenceExpr & subtract(const Term &main_term, const Span< Term > subtract_terms)
IndexMaskSegment shift(const int64_t shift) const
IndexMaskSegment(const OffsetSpan< int64_t, int16_t > span)
static IndexMask from_segments(Span< IndexMaskSegment > segments, LinearAllocator<> &memory)
IndexMask slice_content(IndexRange range) const
void foreach_segment(Fn &&fn, Mode mode=exec_mode::serial) const
uint64_t BitInt
void mix_into_first_expr(ExprFn &&expr, FirstBitSpanT &&first_arg, const BitSpanT &...args)
void copy_from_or(FirstBitSpanT &first_arg, const BitSpanT &...args)
void foreach_1_index(const BitSpanT &data, Fn &&fn)
static CoarseSegment & add_coarse_segment__full(CoarseSegment *prev_segment, const int64_t prev_boundary_index, const int64_t current_boundary_index, CoarseResult &result)
static IndexMaskSegment evaluate_exact_with_indices(const Expr &root_expression, LinearAllocator<> &allocator, const IndexRange bounds, const Span< const Expr * > eval_order)
static void evaluate_coarse_and_split_until_segments_are_short(const Expr &root_expression, const Span< const Expr * > eval_order, Vector< EvaluatedSegment, 16 > &r_evaluated_segments, Vector< IndexRange, 16 > &r_short_unknown_segments)
static IndexMaskSegment union_index_mask_segments(const Span< IndexMaskSegment > segments, const int64_t bounds_min, int16_t *r_values)
static constexpr int64_t segment_size_threshold
IndexMask evaluate_expression(const Expr &expression, LinearAllocator<> &memory)
static IndexMask evaluate_expression_impl(const Expr &root_expression, LinearAllocator<> &memory, const ExactEvalMode exact_eval_mode)
static void sort_course_boundaries(MutableSpan< CourseBoundary > boundaries)
static ExactEvalMode determine_exact_eval_mode(const Expr &root_expression)
static CoarseResult evaluate_coarse(const Expr &root_expression, const Span< const Expr * > eval_order, const std::optional< IndexRange > eval_bounds=std::nullopt)
static IndexMaskSegment evaluate_exact_with_bits(const Expr &root_expression, LinearAllocator<> &allocator, const IndexRange bounds, const Span< const Expr * > eval_order)
static void evaluate_short_unknown_segments_exactly(const Expr &root_expression, const ExactEvalMode exact_eval_mode, const Span< const Expr * > eval_order, const Span< IndexRange > short_unknown_segments, LinearAllocator<> &memory, Vector< EvaluatedSegment, 16 > &r_evaluated_segments)
void index_range_to_mask_segments(const IndexRange range, Vector< IndexMaskSegment, N > &r_segments)
static Span< int16_t > bits_to_indices(const BoundedBitSpan bits, LinearAllocator<> &allocator)
static Vector< const Expr *, inline_expr_array_size > compute_eval_order(const Expr &root_expression)
static IndexMaskSegment intersect_index_mask_segments(const Span< IndexMaskSegment > segments, const int64_t bounds_min, int16_t *r_values)
static CoarseSegment & add_coarse_segment__unknown(CoarseSegment *prev_segment, const int64_t prev_boundary_index, const int64_t current_boundary_index, CoarseResult &result)
static IndexMask evaluated_segments_to_index_mask(MutableSpan< EvaluatedSegment > evaluated_segments, LinearAllocator<> &memory)
static Vector< IndexMaskSegment > build_result_mask_segments(const Span< EvaluatedSegment > evaluated_segments)
static void evaluate_coarse_difference(const Span< DifferenceCourseBoundary > boundaries, CoarseResult &r_result)
static CoarseSegment & add_coarse_segment__copy(CoarseSegment *prev_segment, const int64_t prev_boundary_index, const int64_t current_boundary_index, const IndexMask &copy_from_mask, CoarseResult &result)
static IndexMaskSegment difference_index_mask_segments(const IndexMaskSegment main_segment, const Span< IndexMaskSegment > subtract_segments, const int64_t bounds_min, int16_t *r_values)
static void evaluate_coarse_intersection(const Span< CourseBoundary > boundaries, const int64_t terms_num, CoarseResult &r_result)
static void evaluate_coarse_union(const Span< CourseBoundary > boundaries, CoarseResult &r_result)
constexpr int64_t inline_expr_array_size
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)
__int64 int64_t
Definition BKE_text.h:90
BMesh const char void * data
constexpr IntT ceil_division(const IntT x, const IntT y)
signed short int16_t
Definition BKE_text.h:77
const DifferenceExpr & as_difference() const
const IntersectionExpr & as_intersection() const
const AtomicExpr & as_atomic() const
const UnionExpr & as_union() const