112 segment.full_wrap_loop = cyclic;
119 const std::optional<int> point_start,
120 const std::optional<int> point_end,
121 const std::optional<float> factor_start,
122 const std::optional<float> factor_end,
123 const std::optional<int> inter_index_start,
124 const std::optional<int> inter_index_end)
139 if (inter_index_start) {
152 if (inter_index_end) {
173 const float a1 = co_b[1] - co_a[1];
174 const float b1 = co_a[0] - co_b[0];
175 const float c1 = a1 * co_a[0] + b1 * co_a[1];
177 const float a2 = co_d[1] - co_c[1];
178 const float b2 = co_c[0] - co_d[0];
179 const float c2 = a2 * co_c[0] + b2 * co_c[1];
181 const float det = (a1 * b2 - a2 * b1);
186 const float2 isect((b2 * c1 - b1 * c2) / det, (a1 * c2 - a2 * c1) / det);
205 const float factor_i,
206 const float factor_j,
231 const bool cyclic_i = cyclic[curve_i];
232 const IndexRange curve_points_i = points_by_curve[curve_i];
235 const int point_i1 = curve_points_i[i];
236 const int point_i2 = curve_points_i[(i + 1) % curve_points_i.
size()];
238 const float2 co_i1 = screen_space_positions[point_i1];
239 const float2 co_i2 = screen_space_positions[point_i2];
242 bbox_i.
pad(BBOX_PADDING);
247 const float2 padded_i1 = co_i1 - padding_i;
248 const float2 padded_i2 = co_i2 + padding_i;
253 if (curve_i > curve_j) {
262 const bool cyclic_j = cyclic[curve_j];
263 const IndexRange curve_points_j = points_by_curve[curve_j];
266 const int point_j1 = curve_points_j[j];
267 const int point_j2 = curve_points_j[(j + 1) % curve_points_j.
size()];
270 if (curve_i == curve_j && (point_i1 == point_j1 || point_i1 == point_j2 ||
271 point_i2 == point_j1 || point_i2 == point_j2))
276 const float2 co_j1 = screen_space_positions[point_j1];
277 const float2 co_j2 = screen_space_positions[point_j2];
280 bbox_j.
pad(BBOX_PADDING);
290 const float2 padded_j1 = co_j1 - padding_j;
291 const float2 padded_j2 = co_j2 + padding_j;
295 if (
ELEM(isect.kind, isect.LINE_LINE_CROSS, isect.LINE_LINE_EXACT)) {
301 if (factor_i < 0.0f || factor_i > 1.0f || factor_j < 0.0f || factor_j > 1.0f) {
305 r_inters_per_curves[curve_i].append(r_intersections.
size());
306 r_inters_per_curves[curve_j].append(r_intersections.
size());
340 for (
const int seg_i : all_segments.
index_range()) {
342 const int curve_i =
segment.curve;
346 if (curve_i == inter_start.
curve_i) {
356 if (curve_i == inter_end.
curve_i) {
373 const IndexRange points_k = points_by_curve[curve_k];
374 const Span<int> inters = inters_per_curves[curve_k];
376 const int start_size = all_segments.
size();
378 if (inters.
size() == 0) {
383 if (inters.
size() == 1 && cyclic[curve_k]) {
384 const int int_p = inters.
first();
396 all_segments.
last().full_wrap_loop =
true;
404 const IntersectionPoint &inter1 = intersections[inters[i1]];
405 const IntersectionPoint &inter2 = intersections[inters[i2]];
406 return inter1.parameter_for_curve(curve_k) < inter2.parameter_for_curve(curve_k);
409 if (cyclic[curve_k]) {
410 const int int_p_1 = inters[inter_sorted_ids.
first()];
411 const int int_p_2 = inters[inter_sorted_ids.
last()];
426 const int int_p_1 = inters[inter_sorted_ids.
first()];
442 const int int_p_1 = inters[inter_sorted_ids[inter_id]];
443 const int int_p_2 = inters[inter_sorted_ids[inter_id + 1]];
460 if (!cyclic[curve_k]) {
461 const int int_p_2 = inters[inter_sorted_ids.
last()];
476 return all_segments.
size() - start_size;
486 for (
const int curve_k : points_by_curve.
index_range()) {
488 curve_k, inters_per_curves, points_by_curve, intersections, cyclic, all_segments);
506 if ((parameter_first_end == parameter_second_start) ||
516 if ((parameter_first_start == parameter_second_end) ||
544 for (const int curve_i : curves) {
546 if (cyclic[curve_i]) {
550 const IndexRange segment_range = segment_offsets[curve_i];
552 const int segment_index_first = segment_range.first();
553 const bool reversed_first = segment_reversed[segment_index_first];
554 const Segment &segment_first = segments[segment_index_first];
555 const Side direction_first = reversed_first ? Side::End : Side::Start;
556 const int inter_index_first = segment_first.intersection_index[direction_first];
558 const int segment_index_last = segment_range.last();
559 const bool reversed_last = segment_reversed[segment_index_last];
560 const Segment &segment_last = segments[segment_index_last];
561 const Side direction_last = reversed_last ? Side::Start : Side::End;
562 const int inter_index_last = segment_last.intersection_index[direction_last];
565 if (inter_index_first != -1) {
566 dst_start_caps.span[curve_i] = GP_STROKE_CAP_TYPE_FLAT;
568 if (inter_index_last != -1) {
569 dst_end_caps.span[curve_i] = GP_STROKE_CAP_TYPE_FLAT;
574 dst_start_caps.finish();
575 dst_end_caps.finish();
601 for (const int curve_i : curves) {
602 const IndexRange segment_range = segments_by_curve[curve_i];
604 if (segment_range.size() == 1) {
605 if (segments_to_keep[segment_range.first()]) {
606 segment_connections[segment_range.first()][Side::Start] = SEGMENT_CONNECTION_NULL;
607 segment_connections[segment_range.first()][Side::End] = SEGMENT_CONNECTION_NULL;
612 for (const int segment_i : segment_range.drop_back(1)) {
613 if (!segments_to_keep[segment_i]) {
617 if (segments_to_keep[segment_i + 1]) {
618 segment_connections[segment_i][Side::End] = encode_index_and_side(segment_i + 1,
620 segment_connections[segment_i + 1][Side::Start] = encode_index_and_side(segment_i,
624 segment_connections[segment_i][Side::End] = SEGMENT_CONNECTION_NULL;
628 if (!segments_to_keep[segment_range.last()]) {
632 if (!is_cyclic[curve_i]) {
633 segment_connections[segment_range.first()][Side::Start] = SEGMENT_CONNECTION_NULL;
634 segment_connections[segment_range.last()][Side::End] = SEGMENT_CONNECTION_NULL;
638 if (segments_to_keep[segment_range.first()]) {
639 segment_connections[segment_range.first()][Side::Start] = encode_index_and_side(
640 segment_range.last(), Side::End);
641 segment_connections[segment_range.last()][Side::End] = encode_index_and_side(
642 segment_range.first(), Side::Start);
645 segment_connections[segment_range.last()][Side::End] = SEGMENT_CONNECTION_NULL;
662 segment_offset_data.
append(0);
665 int start_segment = 0;
667 auto get_next_unprocessed_segment = [&]() {
670 const int empty_num = start_segment;
671 const int first_segment = processed_segments.
as_span().drop_front(empty_num).first_index_try(
674 if (first_segment == -1) {
677 return first_segment + empty_num;
681 for (
const int seg_i : all_segments.
index_range()) {
682 if (!segments_to_keep[seg_i]) {
683 processed_segments[seg_i] =
true;
687 start_segment = get_next_unprocessed_segment();
690 while (start_segment != -1) {
694 auto append_segment = [&](
const Segment ¤t_segment,
const bool current_backwards) {
695 if (curve_segments.
size() == 0) {
696 curve_segments.
append(current_segment);
697 curve_segment_reversed.
append(current_backwards);
702 curve_segments.
append(current_segment);
703 curve_segment_reversed.
append(current_backwards);
708 bool current_backwards =
true;
709 int current_i = start_segment;
710 bool curve_done =
false;
711 while (!curve_done) {
723 current_i = next_segment;
724 current_backwards = next_side ==
Side::End;
726 if (next_segment == start_segment) {
733 current_backwards = !current_backwards;
734 const int first_segment = current_i;
738 bool curve_closed =
false;
739 while (!curve_done) {
740 if (processed_segments[current_i] ==
true) {
745 const Segment ¤t_segment = all_segments[current_i];
746 processed_segments[current_i] =
true;
747 append_segment(current_segment, current_backwards);
754 curve_closed =
false;
755 if (curve_segments.
size() == 1) {
756 curve_closed = curve_segments.
last().is_loop();
765 if (next_segment == first_segment) {
772 if (curve_segments.
size() == 1) {
780 if ((parameter_end == parameter_start) ||
800 BLI_assert(!processed_segments[next_segment]);
802 current_i = next_segment;
803 current_backwards = next_side ==
Side::End;
806 segments.
extend(curve_segments);
807 segment_reversed.
extend(curve_segment_reversed);
810 cyclic.
append(curve_closed);
812 start_segment = get_next_unprocessed_segment();
822 for (const int src_curve : src_curves) {
823 Bounds<float2> &bbox = screen_space_bbox[src_curve];
825 const IndexRange src_points = src_points_by_curve[src_curve];
826 bbox = *bounds::min_max(screen_space_positions.slice(src_points));
829 bbox.pad(BBOX_PADDING);
840 for (const int shape_id : shape_ids) {
841 std::optional<Bounds<float2>> bbox;
843 const Span<int> shape = shapes[shape_id];
844 for (const int curve_i : shape) {
845 const IndexRange src_points = src_points_by_curve[curve_i];
846 bbox = bounds::merge(bbox, *bounds::min_max(screen_space_positions.slice(src_points)));
850 bbox->pad(BBOX_PADDING);
852 screen_space_bbox[shape_id] = *bbox;
Low-level operations for curves.
#define BLI_assert_unreachable()
Span< T > as_span() const
const T & last(const int64_t n=0) const
IndexRange index_range() const
constexpr int64_t first() const
constexpr IndexRange shift(int64_t n) const
constexpr IndexRange drop_back(int64_t n) const
constexpr int64_t last(const int64_t n=0) const
constexpr int64_t size() const
constexpr IndexRange()=default
constexpr bool contains(int64_t value) const
constexpr IndexRange index_range() const
static constexpr IndexRange from_begin_end_inclusive(const int64_t begin, const int64_t last)
constexpr const T & first() const
constexpr int64_t size() const
constexpr IndexRange index_range() const
void append(const T &value)
const T & last(const int64_t n=0) const
void extend(Span< T > array)
MutableAttributeAccessor attributes_for_write()
GSpanAttributeWriter lookup_or_add_for_write_span(StringRef name, AttrDomain domain, AttrType data_type, const AttributeInit &initializer=AttributeInitDefaultValue())
int2 edge(Side side) const
bool has_intersection(Side side) const
int wrap_index(int i) const
IndexRange point_range() const
int intersection_index[2]
static Segment from_curve(int curve_i, IndexRange points, bool cyclic)
constexpr Segment()=default
static Segment from_intersections(int curve_i, IndexRange points, const std::optional< int > point_start, const std::optional< int > point_end, const std::optional< float > factor_start, const std::optional< float > factor_end, const std::optional< int > inter_index_start, const std::optional< int > inter_index_end)
float intersection_factor[2]
void foreach_index(Fn &&fn, Mode mode=exec_mode::serial) const
IndexRange index_range() const
float distance(float, float) RET
void fill_index_range(MutableSpan< T > span, const T start=0)
std::optional< Bounds< T > > intersect(const Bounds< T > &a, const Bounds< T > &b)
void cut_caps(bke::CurvesGeometry &dst, const Span< Segment > segments, const Span< bool > segment_reversed, const Span< bool > cyclic, const OffsetIndices< int > segment_offsets)
EncodedConnection encode_index_and_side(const int index, const Side side)
static void find_intersections_between_curve_and_curves(const Span< float2 > screen_space_positions, const Span< Bounds< float2 > > screen_space_bbox, const OffsetIndices< int > points_by_curve, const VArray< bool > &cyclic, const IndexMask &visible_curves, const int curve_i, Array< Vector< int > > &r_inters_per_curves, Vector< IntersectionPoint > &r_intersections)
constexpr EncodedConnection SEGMENT_CONNECTION_NULL
void compute_bounding_boxes(const OffsetIndices< int > src_points_by_curve, const Span< float2 > screen_space_positions, MutableSpan< Bounds< float2 > > screen_space_bbox)
IntersectionPoint create_intersection(const int point_i, const int point_j, const float factor_i, const float factor_j, const int curve_i, const int curve_j)
void create_segments_from_intersections(const Span< Vector< int > > inters_per_curves, const OffsetIndices< int > points_by_curve, const Span< IntersectionPoint > &intersections, const VArray< bool > &cyclic, Vector< Segment > &all_segments, MutableSpan< int > segments_num_per_curve)
void store_segment_map_on_intersections(const Span< Segment > all_segments, MutableSpan< IntersectionPoint > intersections)
int decode_index(const EncodedConnection encoded)
int create_segments_from_intersections_single_curve(const int curve_k, const Span< Vector< int > > inters_per_curves, const OffsetIndices< int > points_by_curve, const Span< IntersectionPoint > &intersections, const VArray< bool > &cyclic, Vector< Segment > &all_segments)
Side decode_side(const EncodedConnection encoded)
void follow_segment_connections(const Span< Segment > all_segments, const Span< bool > segments_to_keep, const Span< SegmentConnections > segment_connections, Vector< Segment > &segments, Vector< int > &segment_offset_data, Vector< bool > &segment_reversed, Vector< bool > &cyclic)
static float get_intersection_distance_of_segments(const float2 &co_a, const float2 &co_b, const float2 &co_c, const float2 &co_d)
static bool check_and_join_segments(Segment &first, const Segment &second)
void find_intersections_between_all_curves(const Span< float2 > screen_space_positions, const Span< Bounds< float2 > > screen_space_bbox, const OffsetIndices< int > points_by_curve, const VArray< bool > &cyclic, const IndexMask &visible_curves, Array< Vector< int > > &r_inters_per_curves, Vector< IntersectionPoint > &r_intersections)
void create_connections_from_curves(const OffsetIndices< int > segments_by_curve, const Span< bool > segments_to_keep, const VArray< bool > &is_cyclic, MutableSpan< SegmentConnections > segment_connections)
T safe_divide(const T &a, const T &b)
isect_result< VecBase< T, Size > > isect_seg_seg(const VecBase< T, Size > &v1, const VecBase< T, Size > &v2, const VecBase< T, Size > &v3, const VecBase< T, Size > &v4)
T distance(const T &a, const T &b)
T min(const T &a, const T &b)
MatBase< T, NumCol, NumRow > normalize(const MatBase< T, NumCol, NumRow > &a)
T mod_periodic(const T &a, const T &b)
T max(const T &a, const T &b)
void parallel_for(const IndexRange range, const int64_t grain_size, const Function &function, const TaskSizeHints &size_hints=detail::TaskSizeHints_Static(1))
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void parallel_sort(RandomAccessIterator begin, RandomAccessIterator end)
VecBase< int32_t, 2 > int2
VecBase< float, 2 > float2
void pad(const PaddingT &padding)
float point_for_curve(const int curve) const
float parameter_for_curve(const int curve) const
float factor_for_curve(const int curve) const
IndexRange index_range() const