diff options
author | Mattias Fredriksson <Osares> | 2022-09-13 19:36:14 +0300 |
---|---|---|
committer | Hans Goudey <h.goudey@me.com> | 2022-09-13 19:36:14 +0300 |
commit | eaf416693dcb431ec122fc559788e6c930038c23 (patch) | |
tree | ecaed24c409442f060b635c8b5fa2991a2e8beb8 | |
parent | d88811aed3cd84cd772d104c97e15fddb466c78d (diff) |
Geometry Nodes: Port the trim curve node to the new data-block
The trim functionality is implemented in the geometry module, and
generalized a bit to be potentially useful for bisecting in the future.
The implementation is based on a helper type called `IndexRangeCyclic`
which allows iteration over all control points between two points on a
curve.
Catmull Rom curves are now supported-- trimmed without resampling first.
However, maintaining the exact shape is not possible. NURBS splines are
still converted to polylines using the evaluated curve concept.
Performance is equivalent or faster then a 3.1 build with regards to
node timings. Compared to 3.3 and 3.2, it's easy to observe test cases
where the node is at least 3 or 4 times faster.
Differential Revision: https://developer.blender.org/D14481
-rw-r--r-- | source/blender/blenkernel/BKE_attribute.hh | 13 | ||||
-rw-r--r-- | source/blender/blenkernel/BKE_curves.hh | 73 | ||||
-rw-r--r-- | source/blender/blenkernel/BKE_curves_utils.hh | 328 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/attribute_access.cc | 32 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/curve_catmull_rom.cc | 14 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_array_utils.hh | 35 | ||||
-rw-r--r-- | source/blender/blenlib/CMakeLists.txt | 2 | ||||
-rw-r--r-- | source/blender/blenlib/intern/array_utils.cc | 18 | ||||
-rw-r--r-- | source/blender/geometry/CMakeLists.txt | 2 | ||||
-rw-r--r-- | source/blender/geometry/GEO_trim_curves.hh | 32 | ||||
-rw-r--r-- | source/blender/geometry/intern/trim_curves.cc | 1285 | ||||
-rw-r--r-- | source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc | 477 |
12 files changed, 1859 insertions, 452 deletions
diff --git a/source/blender/blenkernel/BKE_attribute.hh b/source/blender/blenkernel/BKE_attribute.hh index 21d91af55d5..fbdacee139c 100644 --- a/source/blender/blenkernel/BKE_attribute.hh +++ b/source/blender/blenkernel/BKE_attribute.hh @@ -710,6 +710,19 @@ Vector<AttributeTransferData> retrieve_attributes_for_transfer( eAttrDomainMask domain_mask, const Set<std::string> &skip = {}); +/** + * Copy attributes for the domain based on the elementwise mask. + * + * \param mask_indices: Indexed elements to copy from the source data-block. + * \param domain: Attribute domain to transfer. + * \param skip: Named attributes to ignore/skip. + */ +void copy_attribute_domain(AttributeAccessor src_attributes, + MutableAttributeAccessor dst_attributes, + IndexMask selection, + eAttrDomain domain, + const Set<std::string> &skip = {}); + bool allow_procedural_attribute_access(StringRef attribute_name); extern const char *no_procedural_access_message; diff --git a/source/blender/blenkernel/BKE_curves.hh b/source/blender/blenkernel/BKE_curves.hh index 4b0fc293b54..9f150c13d6e 100644 --- a/source/blender/blenkernel/BKE_curves.hh +++ b/source/blender/blenkernel/BKE_curves.hh @@ -22,6 +22,7 @@ #include "BLI_virtual_array.hh" #include "BKE_attribute.hh" +#include "BKE_attribute_math.hh" namespace blender::bke { @@ -162,6 +163,11 @@ class CurvesGeometry : public ::CurvesGeometry { IndexRange curves_range() const; /** + * Number of control points in the indexed curve. + */ + int points_num_for_curve(const int index) const; + + /** * The index of the first point in every curve. The size of this span is one larger than the * number of curves. Consider using #points_for_curve rather than using the offsets directly. */ @@ -532,6 +538,16 @@ bool segment_is_vector(Span<int8_t> handle_types_left, int segment_index); /** + * True if the Bezier curve contains polygonal segments of HandleType::BEZIER_HANDLE_VECTOR. + * + * \param num_curve_points: Number of points in the curve. + * \param evaluated_size: Number of evaluated points in the curve. + * \param cyclic: If curve is cyclic. + * \param resolution: Curve resolution. + */ +bool has_vector_handles(int num_curve_points, int64_t evaluated_size, bool cyclic, int resolution); + +/** * Return true if the curve's last cyclic segment has a vector type. * This only makes a difference in the shape of cyclic curves. */ @@ -693,6 +709,36 @@ void interpolate_to_evaluated(const GSpan src, const Span<int> evaluated_offsets, GMutableSpan dst); +void calculate_basis(const float parameter, float r_weights[4]); + +/** + * Interpolate the control point values for the given parameter on the piecewise segment. + * \param a: Value associated with the first control point influencing the segment. + * \param d: Value associated with the fourth control point. + * \param parameter: Parameter in range [0, 1] to compute the interpolation for. + */ +template<typename T> +T interpolate(const T &a, const T &b, const T &c, const T &d, const float parameter) +{ + float n[4]; + calculate_basis(parameter, n); + /* TODO: Use DefaultMixer or other generic mixing in the basis evaluation function to simplify + * supporting more types. */ + if constexpr (!is_same_any_v<T, float, float2, float3, float4, int8_t, int, int64_t>) { + T return_value; + attribute_math::DefaultMixer<T> mixer({&return_value, 1}); + mixer.mix_in(0, a, n[0] * 0.5f); + mixer.mix_in(0, b, n[1] * 0.5f); + mixer.mix_in(0, c, n[2] * 0.5f); + mixer.mix_in(0, d, n[3] * 0.5f); + mixer.finalize(); + return return_value; + } + else { + return 0.5f * (a * n[0] + b * n[1] + c * n[2] + d * n[3]); + } +} + } // namespace catmull_rom /** \} */ @@ -807,6 +853,16 @@ inline IndexRange CurvesGeometry::curves_range() const return IndexRange(this->curves_num()); } +inline int CurvesGeometry::points_num_for_curve(const int index) const +{ + BLI_assert(this->curve_num > 0); + BLI_assert(this->curve_num > index); + BLI_assert(this->curve_offsets != nullptr); + const int offset = this->curve_offsets[index]; + const int offset_next = this->curve_offsets[index + 1]; + return offset_next - offset; +} + inline bool CurvesGeometry::is_single_type(const CurveType type) const { return this->curve_type_counts()[type] == this->curves_num(); @@ -833,6 +889,7 @@ inline IndexRange CurvesGeometry::points_for_curve(const int index) const { /* Offsets are not allocated when there are no curves. */ BLI_assert(this->curve_num > 0); + BLI_assert(this->curve_num > index); BLI_assert(this->curve_offsets != nullptr); const int offset = this->curve_offsets[index]; const int offset_next = this->curve_offsets[index + 1]; @@ -905,11 +962,13 @@ inline float CurvesGeometry::evaluated_length_total_for_curve(const int curve_in /** \} */ +namespace curves { + /* -------------------------------------------------------------------- */ /** \name Bezier Inline Methods * \{ */ -namespace curves::bezier { +namespace bezier { inline bool point_is_sharp(const Span<int8_t> handle_types_left, const Span<int8_t> handle_types_right, @@ -929,14 +988,24 @@ inline bool segment_is_vector(const int8_t left, const int8_t right) return segment_is_vector(HandleType(left), HandleType(right)); } +inline bool has_vector_handles(const int num_curve_points, + const int64_t evaluated_size, + const bool cyclic, + const int resolution) +{ + return evaluated_size - !cyclic != (int64_t)segments_num(num_curve_points, cyclic) * resolution; +} + inline float3 calculate_vector_handle(const float3 &point, const float3 &next_point) { return math::interpolate(point, next_point, 1.0f / 3.0f); } +} // namespace bezier + /** \} */ -} // namespace curves::bezier +} // namespace curves struct CurvesSurfaceTransforms { float4x4 curves_to_world; diff --git a/source/blender/blenkernel/BKE_curves_utils.hh b/source/blender/blenkernel/BKE_curves_utils.hh index 0fbd33002e1..5579ab5654a 100644 --- a/source/blender/blenkernel/BKE_curves_utils.hh +++ b/source/blender/blenkernel/BKE_curves_utils.hh @@ -11,9 +11,301 @@ #include "BLI_function_ref.hh" #include "BLI_generic_pointer.hh" +#include "BLI_index_range.hh" namespace blender::bke::curves { +/* -------------------------------------------------------------------- + * Utility structs. + */ + +/** + * Reference to a piecewise segment on a spline curve. + */ +struct CurveSegment { + /** + * Index of the previous control/evaluated point on the curve. First point on the segment. + */ + int index; + /** + * Index of the next control/evaluated point on the curve. Last point on the curve segment. + * Should be 0 for looped segments. + */ + int next_index; +}; + +/** + * Reference to a point on a piecewise curve (spline). + * + * Tracks indices of the neighbouring control/evaluated point pair associated with the segment + * in which the point resides. Referenced point within the segment is defined by a + * normalized parameter in the range [0, 1]. + */ +struct CurvePoint : public CurveSegment { + /** + * Normalized parameter in the range [0, 1] defining the point on the piecewise segment. + * Note that the curve point representation is not unique at segment endpoints. + */ + float parameter; + + /** + * True if the parameter is an integer and references a control/evaluated point. + */ + inline bool is_controlpoint() const; + + /* + * Compare if the points are equal. + */ + inline bool operator==(const CurvePoint &other) const; + inline bool operator!=(const CurvePoint &other) const; + + /** + * Compare if 'this' point comes before 'other'. Loop segment for cyclical curves counts + * as the first (least) segment. + */ + inline bool operator<(const CurvePoint &other) const; +}; + +/** + * Cyclical index range. Iterates the interval [start, end). + */ +class IndexRangeCyclic { + /* Index to the start and end of the iterated range. + */ + int64_t start_ = 0; + int64_t end_ = 0; + /* Index for the start and end of the entire iterable range which contains the iterated range + * (e.g. the point range for an indiviudal spline/curve within the entire Curves point domain). + */ + int64_t range_start_ = 0; + int64_t range_end_ = 0; + /* Number of times the range end is passed when the range is iterated. + */ + int64_t cycles_ = 0; + + constexpr IndexRangeCyclic(int64_t begin, + int64_t end, + int64_t iterable_range_start, + int64_t iterable_range_end, + int64_t cycles) + : start_(begin), + end_(end), + range_start_(iterable_range_start), + range_end_(iterable_range_end), + cycles_(cycles) + { + } + + public: + constexpr IndexRangeCyclic() = default; + ~IndexRangeCyclic() = default; + + constexpr IndexRangeCyclic(int64_t start, int64_t end, IndexRange iterable_range, int64_t cycles) + : start_(start), + end_(end), + range_start_(iterable_range.first()), + range_end_(iterable_range.one_after_last()), + cycles_(cycles) + { + } + + /** + * Create an iterator over the cyclical interval [start_index, end_index). + */ + constexpr IndexRangeCyclic(int64_t start, int64_t end, IndexRange iterable_range) + : start_(start), + end_(end == iterable_range.one_after_last() ? iterable_range.first() : end), + range_start_(iterable_range.first()), + range_end_(iterable_range.one_after_last()), + cycles_(end < start) + { + } + + /** + * Increment the range by adding the given number of indices to the beginning of the range. + */ + constexpr IndexRangeCyclic push_forward(int n) + { + BLI_assert(n >= 0); + int64_t nstart = start_ - n; + int64_t cycles = cycles_; + if (nstart < range_start_) { + + cycles += (int64_t)(n / (range_end_ - range_start_)) + (end_ < nstart) - (end_ < start_); + } + return {nstart, end_, range_start_, range_end_, cycles}; + } + /** + * Increment the range by adding the given number of indices to the end of the range. + */ + constexpr IndexRangeCyclic push_backward(int n) + { + BLI_assert(n >= 0); + int64_t new_end = end_ + n; + int64_t cycles = cycles_; + if (range_end_ <= new_end) { + cycles += (int64_t)(n / (range_end_ - range_start_)) + (new_end < start_) - (end_ < start_); + } + return {start_, new_end, range_start_, range_end_, cycles}; + } + + /** + * Get the index range for the curve buffer. + */ + constexpr IndexRange curve_range() const + { + return IndexRange(range_start_, total_size()); + } + + /** + * Range between the first element up to the end of the range. + */ + constexpr IndexRange range_before_loop() const + { + return IndexRange(start_, size_before_loop()); + } + + /** + * Range between the first element in the iterable range up to the last element in the range. + */ + constexpr IndexRange range_after_loop() const + { + return IndexRange(range_start_, size_after_loop()); + } + + /** + * Size of the entire iterable range. + */ + constexpr int64_t total_size() const + { + return range_end_ - range_start_; + } + + /** + * Number of elements between the first element in the range up to the last element in the curve. + */ + constexpr int64_t size_before_loop() const + { + return range_end_ - start_; + } + + /** + * Number of elements between the first element in the iterable range up to the last element in + * the range. + */ + constexpr int64_t size_after_loop() const + { + return end_ - range_start_; + } + + /** + * Get number of elements iterated by the cyclical index range. + */ + constexpr int64_t size() const + { + if (cycles_ > 0) { + return size_before_loop() + end_ + (cycles_ - 1) * (range_end_ - range_start_); + } + else { + return end_ - start_; + } + } + + /** + * Return the number of times the iterator will cycle before ending. + */ + constexpr int64_t cycles() const + { + return cycles_; + } + + constexpr int64_t first() const + { + return start_; + } + + constexpr int64_t one_after_last() const + { + return end_; + } + + struct CyclicIterator; /* Forward declaration */ + + constexpr CyclicIterator begin() const + { + return CyclicIterator(range_start_, range_end_, start_, 0); + } + + constexpr CyclicIterator end() const + { + return CyclicIterator(range_start_, range_end_, end_, cycles_); + } + + struct CyclicIterator { + int64_t index_, begin_, end_, cycles_; + + constexpr CyclicIterator(int64_t range_begin, int64_t range_end, int64_t index, int64_t cycles) + : index_(index), begin_(range_begin), end_(range_end), cycles_(cycles) + { + BLI_assert(range_begin <= index && index <= range_end); + } + + constexpr CyclicIterator(const CyclicIterator ©) + : index_(copy.index_), begin_(copy.begin_), end_(copy.end_), cycles_(copy.cycles_) + { + } + ~CyclicIterator() = default; + + constexpr CyclicIterator &operator=(const CyclicIterator ©) + { + if (this == ©) { + return *this; + } + index_ = copy.index_; + begin_ = copy.begin_; + end_ = copy.end_; + cycles_ = copy.cycles_; + return *this; + } + constexpr CyclicIterator &operator++() + { + index_++; + if (index_ == end_) { + index_ = begin_; + cycles_++; + } + return *this; + } + + void increment(int64_t n) + { + for (int i = 0; i < n; i++) { + ++*this; + } + } + + constexpr const int64_t &operator*() const + { + return index_; + } + + constexpr bool operator==(const CyclicIterator &other) const + { + return index_ == other.index_ && cycles_ == other.cycles_; + } + constexpr bool operator!=(const CyclicIterator &other) const + { + return !this->operator==(other); + } + }; +}; + +/** \} */ + +/* -------------------------------------------------------------------- + * Utility functions. + */ + /** * Copy the provided point attribute values between all curves in the #curve_ranges index * ranges, assuming that all curves have the same number of control points in #src_curves @@ -88,4 +380,40 @@ void foreach_curve_by_type(const VArray<int8_t> &types, FunctionRef<void(IndexMask)> bezier_fn, FunctionRef<void(IndexMask)> nurbs_fn); +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name #CurvePoint Inline Methods + * \{ */ + +inline bool CurvePoint::is_controlpoint() const +{ + return parameter == 0.0 || parameter == 1.0; +} + +inline bool CurvePoint::operator==(const CurvePoint &other) const +{ + return (parameter == other.parameter && index == other.index) || + (parameter == 1.0 && other.parameter == 0.0 && next_index == other.index) || + (parameter == 0.0 && other.parameter == 1.0 && index == other.next_index); +} +inline bool CurvePoint::operator!=(const CurvePoint &other) const +{ + return !this->operator==(other); +} + +inline bool CurvePoint::operator<(const CurvePoint &other) const +{ + if (index == other.index) { + return parameter < other.parameter; + } + else { + /* Use next index for cyclic comparison due to loop segment < first segment. */ + return next_index < other.next_index && + !(next_index == other.index && parameter == 1.0 && other.parameter == 0.0); + } +} + +/** \} */ + } // namespace blender::bke::curves diff --git a/source/blender/blenkernel/intern/attribute_access.cc b/source/blender/blenkernel/intern/attribute_access.cc index 27c54a3d4a7..1e237da8119 100644 --- a/source/blender/blenkernel/intern/attribute_access.cc +++ b/source/blender/blenkernel/intern/attribute_access.cc @@ -14,6 +14,7 @@ #include "DNA_meshdata_types.h" #include "DNA_pointcloud_types.h" +#include "BLI_array_utils.hh" #include "BLI_color.hh" #include "BLI_math_vec_types.hh" #include "BLI_span.hh" @@ -974,6 +975,37 @@ Vector<AttributeTransferData> retrieve_attributes_for_transfer( return attributes; } +void copy_attribute_domain(const AttributeAccessor src_attributes, + MutableAttributeAccessor dst_attributes, + const IndexMask selection, + const eAttrDomain domain, + const Set<std::string> &skip) +{ + src_attributes.for_all( + [&](const bke::AttributeIDRef &id, const bke::AttributeMetaData &meta_data) { + if (meta_data.domain != domain) { + return true; + } + if (id.is_named() && skip.contains(id.name())) { + return true; + } + if (!id.should_be_kept()) { + return true; + } + + const GVArray src = src_attributes.lookup(id, meta_data.domain); + BLI_assert(src); + + /* Copy attribute. */ + GSpanAttributeWriter dst = dst_attributes.lookup_or_add_for_write_only_span( + id, domain, meta_data.data_type); + array_utils::copy(src, selection, dst.span); + dst.finish(); + + return true; + }); +} + } // namespace blender::bke /** \} */ diff --git a/source/blender/blenkernel/intern/curve_catmull_rom.cc b/source/blender/blenkernel/intern/curve_catmull_rom.cc index 952d59edcf9..dac88948036 100644 --- a/source/blender/blenkernel/intern/curve_catmull_rom.cc +++ b/source/blender/blenkernel/intern/curve_catmull_rom.cc @@ -17,16 +17,14 @@ int calculate_evaluated_num(const int points_num, const bool cyclic, const int r } /* Adapted from Cycles #catmull_rom_basis_eval function. */ -template<typename T> -static T calculate_basis(const T &a, const T &b, const T &c, const T &d, const float parameter) +void calculate_basis(const float parameter, float r_weights[4]) { const float t = parameter; const float s = 1.0f - parameter; - const float n0 = -t * s * s; - const float n1 = 2.0f + t * t * (3.0f * t - 5.0f); - const float n2 = 2.0f + s * s * (3.0f * s - 5.0f); - const float n3 = -s * t * t; - return 0.5f * (a * n0 + b * n1 + c * n2 + d * n3); + r_weights[0] = -t * s * s; + r_weights[1] = 2.0f + t * t * (3.0f * t - 5.0f); + r_weights[2] = 2.0f + s * s * (3.0f * s - 5.0f); + r_weights[3] = -s * t * t; } template<typename T> @@ -35,7 +33,7 @@ static void evaluate_segment(const T &a, const T &b, const T &c, const T &d, Mut const float step = 1.0f / dst.size(); dst.first() = b; for (const int i : dst.index_range().drop_front(1)) { - dst[i] = calculate_basis<T>(a, b, c, d, i * step); + dst[i] = interpolate<T>(a, b, c, d, i * step); } } diff --git a/source/blender/blenlib/BLI_array_utils.hh b/source/blender/blenlib/BLI_array_utils.hh new file mode 100644 index 00000000000..dd65147a926 --- /dev/null +++ b/source/blender/blenlib/BLI_array_utils.hh @@ -0,0 +1,35 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ + +#pragma once + +#include "BLI_generic_span.hh" +#include "BLI_generic_virtual_array.hh" +#include "BLI_index_mask.hh" +#include "BLI_task.hh" + +namespace blender::array_utils { + +/** + * Fill the destination span by copying masked values from the src array. Threaded based on + * grainsize. + */ +void copy(const GVArray &src, IndexMask selection, GMutableSpan dst, int64_t grain_size = 4096); + +/** + * Fill the destination span by copying values from the src array. Threaded based on + * grainsize. + */ +template<typename T> +inline void copy(const Span<T> src, + const IndexMask selection, + MutableSpan<T> dst, + const int64_t grain_size = 4096) +{ + threading::parallel_for(selection.index_range(), grain_size, [&](const IndexRange range) { + for (const int64_t index : selection.slice(range)) { + dst[index] = src[index]; + } + }); +} + +} // namespace blender::array_utils diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index 4a635e34205..470ffebcad4 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -47,6 +47,7 @@ set(SRC intern/array_store.c intern/array_store_utils.c intern/array_utils.c + intern/array_utils.cc intern/astar.c intern/bitmap.c intern/bitmap_draw_2d.c @@ -164,6 +165,7 @@ set(SRC BLI_array_store.h BLI_array_store_utils.h BLI_array_utils.h + BLI_array_utils.hh BLI_asan.h BLI_assert.h BLI_astar.h diff --git a/source/blender/blenlib/intern/array_utils.cc b/source/blender/blenlib/intern/array_utils.cc new file mode 100644 index 00000000000..d4266295944 --- /dev/null +++ b/source/blender/blenlib/intern/array_utils.cc @@ -0,0 +1,18 @@ +#include "BLI_array_utils.hh" +#include "BLI_task.hh" + +namespace blender::array_utils { + +void copy(const GVArray &src, + const IndexMask selection, + GMutableSpan dst, + const int64_t grain_size) +{ + BLI_assert(src.type() == dst.type()); + BLI_assert(src.size() == dst.size()); + threading::parallel_for(selection.index_range(), grain_size, [&](const IndexRange range) { + src.materialize_to_uninitialized(selection.slice(range), dst.data()); + }); +} + +} // namespace blender::array_utils diff --git a/source/blender/geometry/CMakeLists.txt b/source/blender/geometry/CMakeLists.txt index 0f06890cbfa..9e1929b60a8 100644 --- a/source/blender/geometry/CMakeLists.txt +++ b/source/blender/geometry/CMakeLists.txt @@ -27,6 +27,7 @@ set(SRC intern/reverse_uv_sampler.cc intern/set_curve_type.cc intern/subdivide_curves.cc + intern/trim_curves.cc intern/uv_parametrizer.cc GEO_add_curves_on_mesh.hh @@ -41,6 +42,7 @@ set(SRC GEO_reverse_uv_sampler.hh GEO_set_curve_type.hh GEO_subdivide_curves.hh + GEO_trim_curves.hh GEO_uv_parametrizer.h ) diff --git a/source/blender/geometry/GEO_trim_curves.hh b/source/blender/geometry/GEO_trim_curves.hh new file mode 100644 index 00000000000..3c07b5628ea --- /dev/null +++ b/source/blender/geometry/GEO_trim_curves.hh @@ -0,0 +1,32 @@ +#include "BLI_span.hh" + +#include "BKE_curves.hh" +#include "BKE_curves_utils.hh" +#include "BKE_geometry_set.hh" + +namespace blender::geometry { + +/* + * Create a new Curves instance by trimming the input curves. Copying the selected splines + * between the start and end points. + */ +bke::CurvesGeometry trim_curves(const bke::CurvesGeometry &src_curves, + IndexMask selection, + Span<bke::curves::CurvePoint> start_points, + Span<bke::curves::CurvePoint> end_points); + +/** + * Find the point(s) and piecewise segment corresponding to the given distance along the length of + * the curve. Returns points on the evaluated curve for Catmull-Rom and NURBS splines. + * + * \param curves: Curve geometry to sample. + * \param lengths: Distance along the curve on form [0.0, length] to determine the point for. + * \param curve_indices: Curve index to lookup for each 'length', negative index are set to 0. + * \param is_normalized: If true, 'lengths' are normalized to the interval [0.0, 1.0]. + */ +Array<bke::curves::CurvePoint, 12> lookup_curve_points(const bke::CurvesGeometry &curves, + Span<float> lengths, + Span<int64_t> curve_indices, + bool is_normalized); + +} // namespace blender::geometry diff --git a/source/blender/geometry/intern/trim_curves.cc b/source/blender/geometry/intern/trim_curves.cc new file mode 100644 index 00000000000..9b71a95057f --- /dev/null +++ b/source/blender/geometry/intern/trim_curves.cc @@ -0,0 +1,1285 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ + +/** \file + * \ingroup bke + */ + +#include "BLI_array_utils.hh" +#include "BLI_length_parameterize.hh" + +#include "BKE_attribute.hh" +#include "BKE_attribute_math.hh" +#include "BKE_curves.hh" +#include "BKE_curves_utils.hh" +#include "BKE_geometry_set.hh" + +#include "GEO_trim_curves.hh" + +namespace blender::geometry { + +/* -------------------------------------------------------------------- */ +/** \name Curve Enums + * \{ */ + +#define CURVE_TYPE_AS_MASK(curve_type) ((CurveTypeMask)((1 << (int)(curve_type)))) + +typedef enum CurveTypeMask { + CURVE_TYPE_MASK_CATMULL_ROM = (1 << 0), + CURVE_TYPE_MASK_POLY = (1 << 1), + CURVE_TYPE_MASK_BEZIER = (1 << 2), + CURVE_TYPE_MASK_NURBS = (1 << 3), + CURVE_TYPE_MASK_ALL = (1 << 4) - 1 +} CurveTypeMask; + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name #IndexRangeCyclic Utilities + * \{ */ + +/** + * Create a cyclical iterator for all control points within the interval [start_point, end_point] + * including any control point at the start or end point. + * + * \param start_point Point on the curve that define the starting point of the interval. + * \param end_point Point on the curve that define the end point of the interval (included). + * \param points IndexRange for the curve points. + */ +static bke::curves::IndexRangeCyclic get_range_between_endpoints( + const bke::curves::CurvePoint start_point, + const bke::curves::CurvePoint end_point, + const IndexRange points) +{ + const int64_t start_index = start_point.parameter == 0.0 ? start_point.index : + start_point.next_index; + int64_t end_index = end_point.parameter == 0.0 ? end_point.index : end_point.next_index; + int64_t cycles; + + if (end_point.is_controlpoint()) { + ++end_index; + if (end_index > points.last()) { + end_index = points.one_after_last(); + } + /* end_point < start_point but parameter is irrelevant (end_point is controlpoint), and loop + * when equal due to increment. */ + cycles = end_index <= start_index; + } + else { + cycles = end_point < start_point || end_index < start_index; + } + return bke::curves::IndexRangeCyclic(start_index, end_index, points, cycles); +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Lookup Curve Points + * \{ */ + +/** + * Find the point on the curve defined by the distance along the curve. Assumes curve resolution is + * constant for all curve segments and evaluated curve points are uniformly spaced between the + * segment endpoints in relation to the curve parameter. + * + * \param lengths: Accumulated lenght for the evaluated curve. + * \param sample_length: Distance along the curve to determine the CurvePoint for. + * \param cyclic: If curve is cyclic. + * \param resolution: Curve resolution (number of evaluated points per segment). + * \param num_curve_points: Total number of control points in the curve. + * \return: Point on the piecewise segment matching the given distance. + */ +static bke::curves::CurvePoint lookup_curve_point(const Span<float> lengths, + const float sample_length, + const bool cyclic, + const int resolution, + const int num_curve_points) +{ + BLI_assert(!cyclic || lengths.size() / resolution >= 2); + const int last_index = num_curve_points - 1; + if (sample_length <= 0.0f) { + return {0, 1, 0.0f}; + } + if (sample_length >= lengths.last()) { + return cyclic ? bke::curves::CurvePoint{last_index, 0, 1.0} : + bke::curves::CurvePoint{last_index - 1, last_index, 1.0}; + } + int eval_index; + float eval_factor; + length_parameterize::sample_at_length(lengths, sample_length, eval_index, eval_factor); + + const int index = eval_index / resolution; + const int next_index = (index == last_index) ? 0 : index + 1; + const float parameter = (eval_factor + eval_index) / resolution - index; + + return bke::curves::CurvePoint{index, next_index, parameter}; +} + +/** + * Find the point on the 'evaluated' polygonal curve. + */ +static bke::curves::CurvePoint lookup_evaluated_point(const Span<float> lengths, + const float sample_length, + const bool cyclic, + const int evaluated_size) +{ + const int last_index = evaluated_size - 1; + if (sample_length <= 0.0f) { + return {0, 1, 0.0f}; + } + if (sample_length >= lengths.last()) { + return cyclic ? bke::curves::CurvePoint{last_index, 0, 1.0} : + bke::curves::CurvePoint{last_index - 1, last_index, 1.0}; + } + + int eval_index; + float eval_factor; + length_parameterize::sample_at_length(lengths, sample_length, eval_index, eval_factor); + + const int next_eval_index = (eval_index == last_index) ? 0 : eval_index + 1; + return bke::curves::CurvePoint{eval_index, next_eval_index, eval_factor}; +} + +/** + * Find the point on a Bezier curve using the 'bezier_offsets' cache. + */ +static bke::curves::CurvePoint lookup_bezier_point(const Span<int> bezier_offsets, + const Span<float> lengths, + const float sample_length, + const bool cyclic, + const int num_curve_points) +{ + const int last_index = num_curve_points - 1; + if (sample_length <= 0.0f) { + return {0, 1, 0.0f}; + } + if (sample_length >= lengths.last()) { + return cyclic ? bke::curves::CurvePoint{last_index, 0, 1.0} : + bke::curves::CurvePoint{last_index - 1, last_index, 1.0}; + } + int eval_index; + float eval_factor; + length_parameterize::sample_at_length(lengths, sample_length, eval_index, eval_factor); + + /* Find the segment index from the offset mapping. */ + const int *offset = std::upper_bound(bezier_offsets.begin(), bezier_offsets.end(), eval_index); + const int left = offset - bezier_offsets.begin(); + const int right = left == last_index ? 0 : left + 1; + + const int prev_offset = left == 0 ? 0 : bezier_offsets[(int64_t)left - 1]; + const float offset_in_segment = eval_factor + eval_index - prev_offset; + const int segment_resolution = bezier_offsets[left] - prev_offset; + const float parameter = std::clamp(offset_in_segment / segment_resolution, 0.0f, 1.0f); + + return {left, right, parameter}; +} + +Array<bke::curves::CurvePoint, 12> lookup_curve_points(const bke::CurvesGeometry &curves, + const Span<float> lengths, + const Span<int64_t> curve_indices, + const bool normalized_factors) +{ + BLI_assert(lengths.size() == curve_indices.size()); + BLI_assert(*std::max_element(curve_indices.begin(), curve_indices.end()) < curves.curves_num()); + + const VArray<bool> cyclic = curves.cyclic(); + const VArray<int> resolution = curves.resolution(); + const VArray<int8_t> curve_types = curves.curve_types(); + + /* Compute curve lenghts! */ + curves.ensure_evaluated_lengths(); + curves.ensure_evaluated_offsets(); + + /* Find the curve points referenced by the input! */ + Array<bke::curves::CurvePoint, 12> lookups(curve_indices.size()); + threading::parallel_for(curve_indices.index_range(), 128, [&](const IndexRange range) { + for (const int64_t lookup_index : range) { + const int64_t curve_i = curve_indices[lookup_index]; + + const int point_count = curves.points_num_for_curve(curve_i); + if (curve_i < 0 || point_count == 1) { + lookups[lookup_index] = {0, 0, 0.0f}; + continue; + } + + const Span<float> accumulated_lengths = curves.evaluated_lengths_for_curve(curve_i, + cyclic[curve_i]); + BLI_assert(accumulated_lengths.size() > 0); + + const float sample_length = normalized_factors ? + lengths[lookup_index] * accumulated_lengths.last() : + lengths[lookup_index]; + + const CurveType curve_type = (CurveType)curve_types[curve_i]; + + switch (curve_type) { + case CURVE_TYPE_BEZIER: { + if (bke::curves::bezier::has_vector_handles( + point_count, + curves.evaluated_points_for_curve(curve_i).size(), + cyclic[curve_i], + resolution[curve_i])) { + const Span<int> bezier_offsets = curves.bezier_evaluated_offsets_for_curve(curve_i); + lookups[lookup_index] = lookup_bezier_point( + bezier_offsets, accumulated_lengths, sample_length, cyclic[curve_i], point_count); + } + else { + lookups[lookup_index] = lookup_curve_point(accumulated_lengths, + sample_length, + cyclic[curve_i], + resolution[curve_i], + point_count); + } + break; + } + case CURVE_TYPE_CATMULL_ROM: { + lookups[lookup_index] = lookup_curve_point(accumulated_lengths, + sample_length, + cyclic[curve_i], + resolution[curve_i], + point_count); + break; + } + case CURVE_TYPE_NURBS: + case CURVE_TYPE_POLY: + default: { + /* Handle general case as an "evaluated" or polygonal curve. */ + BLI_assert(resolution[curve_i] > 0); + lookups[lookup_index] = lookup_evaluated_point( + accumulated_lengths, + sample_length, + cyclic[curve_i], + curves.evaluated_points_for_curve(curve_i).size()); + break; + } + } + } + }); + return lookups; +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Transfer Curve Domain + * \{ */ + +/** + * Determine curve type(s) for the copied curves given the supported set of types and knot modes. + * If a curve type is not supported the default type is set. + */ +static void determine_copyable_curve_types(const bke::CurvesGeometry &src_curves, + bke::CurvesGeometry &dst_curves, + const IndexMask selection, + const IndexMask selection_inverse, + const CurveTypeMask supported_curve_type_mask, + const int8_t default_curve_type = (int8_t) + CURVE_TYPE_POLY) +{ + const VArray<int8_t> src_curve_types = src_curves.curve_types(); + const VArray<int8_t> src_knot_modes = src_curves.nurbs_knots_modes(); + MutableSpan<int8_t> dst_curve_types = dst_curves.curve_types_for_write(); + + threading::parallel_for(selection.index_range(), 4096, [&](const IndexRange selection_range) { + for (const int64_t curve_i : selection.slice(selection_range)) { + if (supported_curve_type_mask & CURVE_TYPE_AS_MASK(src_curve_types[curve_i])) { + dst_curve_types[curve_i] = src_curve_types[curve_i]; + } + else { + dst_curve_types[curve_i] = default_curve_type; + } + } + }); + + array_utils::copy(src_curve_types, selection_inverse, dst_curve_types); +} + +/** + * Determine if a curve is treated as an evaluated curve. Curves which inheretly do not support + * trimming are discretized (e.g. NURBS). + */ +static bool copy_as_evaluated_curve(const int8_t src_type, const int8_t dst_type) +{ + return src_type != CURVE_TYPE_POLY && dst_type == CURVE_TYPE_POLY; +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Specialized Curve Constructors + * \{ */ + +static void compute_trim_result_offsets(const bke::CurvesGeometry &src_curves, + const IndexMask selection, + const IndexMask inverse_selection, + const Span<bke::curves::CurvePoint> start_points, + const Span<bke::curves::CurvePoint> end_points, + const VArray<int8_t> dst_curve_types, + MutableSpan<int> dst_curve_offsets, + Vector<int64_t> &r_curve_indices, + Vector<int64_t> &r_point_curve_indices) +{ + BLI_assert(r_curve_indices.size() == 0); + BLI_assert(r_point_curve_indices.size() == 0); + const VArray<bool> cyclic = src_curves.cyclic(); + const VArray<int8_t> curve_types = src_curves.curve_types(); + r_curve_indices.reserve(selection.size()); + + for (const int64_t curve_i : selection) { + + int64_t src_point_count; + + if (copy_as_evaluated_curve(curve_types[curve_i], dst_curve_types[curve_i])) { + src_point_count = src_curves.evaluated_points_for_curve(curve_i).size(); + } + else { + src_point_count = (int64_t)src_curves.points_num_for_curve(curve_i); + } + BLI_assert(src_point_count > 0); + + if (start_points[curve_i] == end_points[curve_i]) { + dst_curve_offsets[curve_i] = 1; + r_point_curve_indices.append(curve_i); + } + else { + const bke::curves::IndexRangeCyclic point_range = get_range_between_endpoints( + start_points[curve_i], end_points[curve_i], {0, src_point_count}); + const int count = point_range.size() + !start_points[curve_i].is_controlpoint() + + !end_points[curve_i].is_controlpoint(); + dst_curve_offsets[curve_i] = count; + r_curve_indices.append(curve_i); + } + BLI_assert(dst_curve_offsets[curve_i] > 0); + } + threading::parallel_for( + inverse_selection.index_range(), 4096, [&](const IndexRange selection_range) { + for (const int64_t curve_i : inverse_selection.slice(selection_range)) { + dst_curve_offsets[curve_i] = src_curves.points_num_for_curve(curve_i); + } + }); + bke::curves::accumulate_counts_to_offsets(dst_curve_offsets); +} + +/* -------------------------------------------------------------------- + * Utility functions. + */ + +static void fill_bezier_data(bke::CurvesGeometry &dst_curves, const IndexMask selection) +{ + if (dst_curves.has_curve_with_type(CURVE_TYPE_BEZIER)) { + MutableSpan<float3> handle_positions_left = dst_curves.handle_positions_left_for_write(); + MutableSpan<float3> handle_positions_right = dst_curves.handle_positions_right_for_write(); + MutableSpan<int8_t> handle_types_left = dst_curves.handle_types_left_for_write(); + MutableSpan<int8_t> handle_types_right = dst_curves.handle_types_right_for_write(); + + threading::parallel_for(selection.index_range(), 4096, [&](const IndexRange range) { + for (const int64_t curve_i : selection.slice(range)) { + const IndexRange points = dst_curves.points_for_curve(curve_i); + handle_types_right.slice(points).fill((int8_t)BEZIER_HANDLE_FREE); + handle_types_left.slice(points).fill((int8_t)BEZIER_HANDLE_FREE); + handle_positions_left.slice(points).fill({0.0f, 0.0f, 0.0f}); + handle_positions_right.slice(points).fill({0.0f, 0.0f, 0.0f}); + } + }); + } +} +static void fill_nurbs_data(bke::CurvesGeometry &dst_curves, const IndexMask selection) +{ + if (dst_curves.has_curve_with_type(CURVE_TYPE_NURBS)) { + bke::curves::fill_points(dst_curves, selection, 0.0f, dst_curves.nurbs_weights_for_write()); + } +} + +template<typename T> +static int64_t copy_point_data_between_endpoints(const Span<T> src_data, + MutableSpan<T> dst_data, + const bke::curves::IndexRangeCyclic src_range, + const int64_t src_index, + int64_t dst_index) +{ + int64_t increment; + if (src_range.cycles()) { + increment = src_range.size_before_loop(); + dst_data.slice(dst_index, increment).copy_from(src_data.slice(src_index, increment)); + dst_index += increment; + + increment = src_range.size_after_loop(); + dst_data.slice(dst_index, increment) + .copy_from(src_data.slice(src_range.curve_range().first(), increment)); + dst_index += increment; + } + else { + increment = src_range.one_after_last() - src_range.first(); + dst_data.slice(dst_index, increment).copy_from(src_data.slice(src_index, increment)); + dst_index += increment; + } + return dst_index; +} + +/* -------------------------------------------------------------------- + * Sampling utilities. + */ + +template<typename T> +static T interpolate_catmull_rom(const Span<T> src_data, + const bke::curves::CurvePoint insertion_point, + const bool src_cyclic) +{ + BLI_assert(insertion_point.index >= 0 && insertion_point.next_index < src_data.size()); + int i0; + if (insertion_point.index == 0) { + i0 = src_cyclic ? src_data.size() - 1 : insertion_point.index; + } + else { + i0 = insertion_point.index - 1; + } + int i3 = insertion_point.next_index + 1; + if (i3 == src_data.size()) { + i3 = src_cyclic ? 0 : insertion_point.next_index; + } + return bke::curves::catmull_rom::interpolate<T>(src_data[i0], + src_data[insertion_point.index], + src_data[insertion_point.next_index], + src_data[i3], + insertion_point.parameter); +} + +static bke::curves::bezier::Insertion knot_insert_bezier( + const Span<float3> positions, + const Span<float3> handles_left, + const Span<float3> handles_right, + const bke::curves::CurvePoint insertion_point) +{ + BLI_assert( + insertion_point.index + 1 == insertion_point.next_index || + (insertion_point.next_index >= 0 && insertion_point.next_index < insertion_point.index)); + return bke::curves::bezier::insert(positions[insertion_point.index], + handles_right[insertion_point.index], + handles_left[insertion_point.next_index], + positions[insertion_point.next_index], + insertion_point.parameter); +} + +/* -------------------------------------------------------------------- + * Sample single point. + */ + +template<typename T> +static void sample_linear(const Span<T> src_data, + MutableSpan<T> dst_data, + const IndexRange dst_range, + const bke::curves::CurvePoint sample_point) +{ + BLI_assert(dst_range.size() == 1); + if (sample_point.is_controlpoint()) { + /* Resolves cases where the source curve consist of a single control point. */ + const int index = sample_point.parameter == 1.0 ? sample_point.next_index : sample_point.index; + dst_data[dst_range.first()] = src_data[index]; + } + else { + dst_data[dst_range.first()] = attribute_math::mix2( + sample_point.parameter, src_data[sample_point.index], src_data[sample_point.next_index]); + } +} + +template<typename T> +static void sample_catmull_rom(const Span<T> src_data, + MutableSpan<T> dst_data, + const IndexRange dst_range, + const bke::curves::CurvePoint sample_point, + const bool src_cyclic) +{ + BLI_assert(dst_range.size() == 1); + if (sample_point.is_controlpoint()) { + /* Resolves cases where the source curve consist of a single control point. */ + const int index = sample_point.parameter == 1.0 ? sample_point.next_index : sample_point.index; + dst_data[dst_range.first()] = src_data[index]; + } + else { + dst_data[dst_range.first()] = interpolate_catmull_rom(src_data, sample_point, src_cyclic); + } +} + +static void sample_bezier(const Span<float3> src_positions, + const Span<float3> src_handles_l, + const Span<float3> src_handles_r, + const Span<int8_t> src_types_l, + const Span<int8_t> src_types_r, + MutableSpan<float3> dst_positions, + MutableSpan<float3> dst_handles_l, + MutableSpan<float3> dst_handles_r, + MutableSpan<int8_t> dst_types_l, + MutableSpan<int8_t> dst_types_r, + const IndexRange dst_range, + const bke::curves::CurvePoint sample_point) +{ + BLI_assert(dst_range.size() == 1); + if (sample_point.is_controlpoint()) { + /* Resolves cases where the source curve consist of a single control point. */ + const int index = sample_point.parameter == 1.0 ? sample_point.next_index : sample_point.index; + dst_positions[dst_range.first()] = src_positions[index]; + dst_handles_l[dst_range.first()] = src_handles_l[index]; + dst_handles_r[dst_range.first()] = src_handles_r[index]; + dst_types_l[dst_range.first()] = src_types_l[index]; + dst_types_r[dst_range.first()] = src_types_r[index]; + } + else { + bke::curves::bezier::Insertion insertion_point = knot_insert_bezier( + src_positions, src_handles_l, src_handles_r, sample_point); + dst_positions[dst_range.first()] = insertion_point.position; + dst_handles_l[dst_range.first()] = insertion_point.left_handle; + dst_handles_r[dst_range.first()] = insertion_point.right_handle; + dst_types_l[dst_range.first()] = BEZIER_HANDLE_FREE; + dst_types_r[dst_range.first()] = BEZIER_HANDLE_FREE; + } +} + +/* -------------------------------------------------------------------- + * Sample curve interval (trim). + */ + +/** + * Sample source curve data in the interval defined by the points [start_point, end_point]. + * Uses linear interpolation to compute the endpoints. + * + * \tparam include_start_point If False, the 'start_point' point sample will not be copied + * and not accounted for in the destination range. + * \param src_data: Source to sample from. + * \param dst_data: Destination to write samples to. + * \param src_range: Interval within [start_point, end_point] to copy from the source point domain. + * \param dst_range: Interval to copy point data to in the destination buffer. + * \param start_point: Point on the source curve to start sampling from. + * \param end_point: Last point to sample in the source curve. + */ +template<typename T, bool include_start_point = true> +static void sample_interval_linear(const Span<T> src_data, + MutableSpan<T> dst_data, + const bke::curves::IndexRangeCyclic src_range, + const IndexRange dst_range, + const bke::curves::CurvePoint start_point, + const bke::curves::CurvePoint end_point) +{ + int64_t src_index = src_range.first(); + int64_t dst_index = dst_range.first(); + + if (start_point.is_controlpoint()) { + /* 'start_point' is included in the copy iteration. */ + if constexpr (!include_start_point) { + /* Skip first. */ + ++src_index; + } + } + else if constexpr (!include_start_point) { + /* Do nothing (excluded). */ + } + else { + /* General case, sample 'start_point' */ + dst_data[dst_index] = attribute_math::mix2( + start_point.parameter, src_data[start_point.index], src_data[start_point.next_index]); + ++dst_index; + } + + dst_index = copy_point_data_between_endpoints( + src_data, dst_data, src_range, src_index, dst_index); + + /* Handle last case */ + if (end_point.is_controlpoint()) { + /* 'end_point' is included in the copy iteration. */ + } + else { + dst_data[dst_index] = attribute_math::mix2( + end_point.parameter, src_data[end_point.index], src_data[end_point.next_index]); +#ifdef DEBUG + ++dst_index; +#endif + } + BLI_assert(dst_index == dst_range.one_after_last()); +} + +template<typename T, bool include_start_point = true> +static void sample_interval_catmull_rom(const Span<T> src_data, + MutableSpan<T> dst_data, + const bke::curves::IndexRangeCyclic src_range, + const IndexRange dst_range, + const bke::curves::CurvePoint start_point, + const bke::curves::CurvePoint end_point, + const bool src_cyclic) +{ + int64_t src_index = src_range.first(); + int64_t dst_index = dst_range.first(); + + if (start_point.is_controlpoint()) { + /* 'start_point' is included in the copy iteration. */ + if constexpr (!include_start_point) { + /* Skip first. */ + ++src_index; + } + } + else if constexpr (!include_start_point) { + /* Do nothing (excluded). */ + } + else { + /* General case, sample 'start_point' */ + dst_data[dst_index] = interpolate_catmull_rom(src_data, start_point, src_cyclic); + ++dst_index; + } + + dst_index = copy_point_data_between_endpoints( + src_data, dst_data, src_range, src_index, dst_index); + + /* Handle last case */ + if (end_point.is_controlpoint()) { + /* 'end_point' is included in the copy iteration. */ + } + else { + dst_data[dst_index] = interpolate_catmull_rom(src_data, end_point, src_cyclic); +#ifdef DEBUG + ++dst_index; +#endif + } + BLI_assert(dst_index == dst_range.one_after_last()); +} + +template<bool include_start_point = true> +static void sample_interval_bezier(const Span<float3> src_positions, + const Span<float3> src_handles_l, + const Span<float3> src_handles_r, + const Span<int8_t> src_types_l, + const Span<int8_t> src_types_r, + MutableSpan<float3> dst_positions, + MutableSpan<float3> dst_handles_l, + MutableSpan<float3> dst_handles_r, + MutableSpan<int8_t> dst_types_l, + MutableSpan<int8_t> dst_types_r, + const bke::curves::IndexRangeCyclic src_range, + const IndexRange dst_range, + const bke::curves::CurvePoint start_point, + const bke::curves::CurvePoint end_point) +{ + bke::curves::bezier::Insertion start_point_insert; + int64_t src_index = src_range.first(); + int64_t dst_index = dst_range.first(); + + bool start_point_trimmed = false; + if (start_point.is_controlpoint()) { + /* The 'start_point' control point is included in the copy iteration. */ + if constexpr (!include_start_point) { + ++src_index; /* Skip first! */ + } + } + else if constexpr (!include_start_point) { + /* Do nothing, 'start_point' is excluded. */ + } + else { + /* General case, sample 'start_point'. */ + start_point_insert = knot_insert_bezier( + src_positions, src_handles_l, src_handles_r, start_point); + dst_positions[dst_range.first()] = start_point_insert.position; + dst_handles_l[dst_range.first()] = start_point_insert.left_handle; + dst_handles_r[dst_range.first()] = start_point_insert.right_handle; + dst_types_l[dst_range.first()] = src_types_l[start_point.index]; + dst_types_r[dst_range.first()] = src_types_r[start_point.index]; + + start_point_trimmed = true; + ++dst_index; + } + + /* Copy point data between the 'start_point' and 'end_point'. */ + int64_t increment = src_range.cycles() ? src_range.size_before_loop() : + src_range.one_after_last() - src_range.first(); + + const IndexRange dst_range_to_end(dst_index, increment); + const IndexRange src_range_to_end(src_index, increment); + dst_positions.slice(dst_range_to_end).copy_from(src_positions.slice(src_range_to_end)); + dst_handles_l.slice(dst_range_to_end).copy_from(src_handles_l.slice(src_range_to_end)); + dst_handles_r.slice(dst_range_to_end).copy_from(src_handles_r.slice(src_range_to_end)); + dst_types_l.slice(dst_range_to_end).copy_from(src_types_l.slice(src_range_to_end)); + dst_types_r.slice(dst_range_to_end).copy_from(src_types_r.slice(src_range_to_end)); + dst_index += increment; + + increment = src_range.size_after_loop(); + if (src_range.cycles() && increment > 0) { + const IndexRange dst_range_looped(dst_index, increment); + const IndexRange src_range_looped(src_range.curve_range().first(), increment); + dst_positions.slice(dst_range_looped).copy_from(src_positions.slice(src_range_looped)); + dst_handles_l.slice(dst_range_looped).copy_from(src_handles_l.slice(src_range_looped)); + dst_handles_r.slice(dst_range_looped).copy_from(src_handles_r.slice(src_range_looped)); + dst_types_l.slice(dst_range_looped).copy_from(src_types_l.slice(src_range_looped)); + dst_types_r.slice(dst_range_looped).copy_from(src_types_r.slice(src_range_looped)); + dst_index += increment; + } + + if (start_point_trimmed) { + dst_handles_l[dst_range.first() + 1] = start_point_insert.handle_next; + /* No need to set handle type (remains the same)! */ + } + + /* Handle 'end_point' */ + bke::curves::bezier::Insertion end_point_insert; + if (end_point.is_controlpoint()) { + /* Do nothing, the 'end_point' control point is included in the copy iteration. */ + } + else { + /* Trimmed in both ends within the same (and only) segment! Ensure both end points is not a + * loop.*/ + if (start_point_trimmed && start_point.index == end_point.index && + start_point.parameter <= end_point.parameter) { + + /* Copy following segment control point. */ + dst_positions[dst_index] = src_positions[end_point.next_index]; + dst_handles_r[dst_index] = src_handles_r[end_point.next_index]; + + /* Compute interpolation in the result curve. */ + const float parameter = (end_point.parameter - start_point.parameter) / + (1.0f - start_point.parameter); + end_point_insert = knot_insert_bezier( + dst_positions, + dst_handles_l, + dst_handles_r, + {(int)dst_range.first(), (int)(dst_range.first() + 1), parameter}); + } + else { + /* General case, compute the insertion point. */ + end_point_insert = knot_insert_bezier( + src_positions, src_handles_l, src_handles_r, end_point); + } + + dst_handles_r[dst_index - 1] = end_point_insert.handle_prev; + dst_types_r[dst_index - 1] = src_types_l[end_point.index]; + + dst_handles_l[dst_index] = end_point_insert.left_handle; + dst_handles_r[dst_index] = end_point_insert.right_handle; + dst_positions[dst_index] = end_point_insert.position; + dst_types_l[dst_index] = src_types_l[end_point.next_index]; + dst_types_r[dst_index] = src_types_r[end_point.next_index]; +#ifdef DEBUG + ++dst_index; +#endif // DEBUG + } + BLI_assert(dst_index == dst_range.one_after_last()); +} + +/* -------------------------------------------------------------------- + * Convert to point curves. + */ + +static void convert_point_polygonal_curves( + const bke::CurvesGeometry &src_curves, + bke::CurvesGeometry &dst_curves, + const IndexMask selection, + const Span<bke::curves::CurvePoint> sample_points, + MutableSpan<bke::AttributeTransferData> transfer_attributes) +{ + const Span<float3> src_positions = src_curves.positions(); + MutableSpan<float3> dst_positions = dst_curves.positions_for_write(); + + threading::parallel_for(selection.index_range(), 4096, [&](const IndexRange range) { + for (const int64_t curve_i : selection.slice(range)) { + const IndexRange src_points = src_curves.points_for_curve(curve_i); + const IndexRange dst_points = dst_curves.points_for_curve(curve_i); + + sample_linear<float3>( + src_positions.slice(src_points), dst_positions, dst_points, sample_points[curve_i]); + + for (bke::AttributeTransferData &attribute : transfer_attributes) { + attribute_math::convert_to_static_type(attribute.meta_data.data_type, [&](auto dummy) { + using T = decltype(dummy); + sample_linear<T>(attribute.src.template typed<T>().slice(src_points), + attribute.dst.span.typed<T>(), + dst_curves.points_for_curve(curve_i), + sample_points[curve_i]); + }); + } + } + }); + + fill_bezier_data(dst_curves, selection); + fill_nurbs_data(dst_curves, selection); +} + +static void convert_point_catmull_curves( + const bke::CurvesGeometry &src_curves, + bke::CurvesGeometry &dst_curves, + const IndexMask selection, + const Span<bke::curves::CurvePoint> sample_points, + MutableSpan<bke::AttributeTransferData> transfer_attributes) +{ + const Span<float3> src_positions = src_curves.positions(); + const VArray<bool> src_cyclic = src_curves.cyclic(); + + MutableSpan<float3> dst_positions = dst_curves.positions_for_write(); + + threading::parallel_for(selection.index_range(), 4096, [&](const IndexRange range) { + for (const int64_t curve_i : selection.slice(range)) { + const IndexRange src_points = src_curves.points_for_curve(curve_i); + const IndexRange dst_points = dst_curves.points_for_curve(curve_i); + + sample_catmull_rom<float3>(src_positions.slice(src_points), + dst_positions, + dst_points, + sample_points[curve_i], + src_cyclic[curve_i]); + for (bke::AttributeTransferData &attribute : transfer_attributes) { + attribute_math::convert_to_static_type(attribute.meta_data.data_type, [&](auto dummy) { + using T = decltype(dummy); + sample_catmull_rom<T>(attribute.src.template typed<T>().slice(src_points), + attribute.dst.span.typed<T>(), + dst_points, + sample_points[curve_i], + src_cyclic[curve_i]); + }); + } + } + }); + fill_bezier_data(dst_curves, selection); + fill_nurbs_data(dst_curves, selection); +} + +static void convert_point_bezier_curves( + const bke::CurvesGeometry &src_curves, + bke::CurvesGeometry &dst_curves, + const IndexMask selection, + const Span<bke::curves::CurvePoint> sample_points, + MutableSpan<bke::AttributeTransferData> transfer_attributes) +{ + const Span<float3> src_positions = src_curves.positions(); + const VArraySpan<int8_t> src_types_l{src_curves.handle_types_left()}; + const VArraySpan<int8_t> src_types_r{src_curves.handle_types_right()}; + const Span<float3> src_handles_l = src_curves.handle_positions_left(); + const Span<float3> src_handles_r = src_curves.handle_positions_right(); + + MutableSpan<float3> dst_positions = dst_curves.positions_for_write(); + MutableSpan<int8_t> dst_types_l = dst_curves.handle_types_left_for_write(); + MutableSpan<int8_t> dst_types_r = dst_curves.handle_types_right_for_write(); + MutableSpan<float3> dst_handles_l = dst_curves.handle_positions_left_for_write(); + MutableSpan<float3> dst_handles_r = dst_curves.handle_positions_right_for_write(); + + threading::parallel_for(selection.index_range(), 4096, [&](const IndexRange range) { + for (const int64_t curve_i : selection.slice(range)) { + const IndexRange src_points = src_curves.points_for_curve(curve_i); + const IndexRange dst_points = dst_curves.points_for_curve(curve_i); + + sample_bezier(src_positions.slice(src_points), + src_handles_l.slice(src_points), + src_handles_r.slice(src_points), + src_types_l.slice(src_points), + src_types_r.slice(src_points), + dst_positions, + dst_handles_l, + dst_handles_r, + dst_types_l, + dst_types_r, + dst_points, + sample_points[curve_i]); + + for (bke::AttributeTransferData &attribute : transfer_attributes) { + attribute_math::convert_to_static_type(attribute.meta_data.data_type, [&](auto dummy) { + using T = decltype(dummy); + sample_linear<T>(attribute.src.template typed<T>().slice(src_points), + attribute.dst.span.typed<T>(), + dst_points, + sample_points[curve_i]); + }); + } + } + }); + fill_nurbs_data(dst_curves, selection); +} + +static void convert_point_evaluated_curves( + const bke::CurvesGeometry &src_curves, + bke::CurvesGeometry &dst_curves, + const IndexMask selection, + const Span<bke::curves::CurvePoint> evaluated_sample_points, + MutableSpan<bke::AttributeTransferData> transfer_attributes) +{ + const Span<float3> src_eval_positions = src_curves.evaluated_positions(); + MutableSpan<float3> dst_positions = dst_curves.positions_for_write(); + + threading::parallel_for(selection.index_range(), 4096, [&](const IndexRange range) { + for (const int64_t curve_i : selection.slice(range)) { + const IndexRange dst_points = dst_curves.points_for_curve(curve_i); + const IndexRange src_evaluated_points = src_curves.evaluated_points_for_curve(curve_i); + + sample_linear<float3>(src_eval_positions.slice(src_evaluated_points), + dst_positions, + dst_points, + evaluated_sample_points[curve_i]); + + for (bke::AttributeTransferData &attribute : transfer_attributes) { + attribute_math::convert_to_static_type(attribute.meta_data.data_type, [&](auto dummy) { + using T = decltype(dummy); + GArray evaluated_data(CPPType::get<T>(), src_evaluated_points.size()); + GMutableSpan evaluated_span = evaluated_data.as_mutable_span(); + src_curves.interpolate_to_evaluated( + curve_i, attribute.src.slice(src_curves.points_for_curve(curve_i)), evaluated_span); + sample_linear<T>(evaluated_span.typed<T>(), + attribute.dst.span.typed<T>(), + dst_points, + evaluated_sample_points[curve_i]); + }); + } + } + }); + fill_bezier_data(dst_curves, selection); + fill_nurbs_data(dst_curves, selection); +} + +/* -------------------------------------------------------------------- + * Trim curves. + */ + +static void trim_attribute_linear(const bke::CurvesGeometry &src_curves, + bke::CurvesGeometry &dst_curves, + const IndexMask selection, + const Span<bke::curves::CurvePoint> start_points, + const Span<bke::curves::CurvePoint> end_points, + MutableSpan<bke::AttributeTransferData> transfer_attributes) +{ + for (bke::AttributeTransferData &attribute : transfer_attributes) { + attribute_math::convert_to_static_type(attribute.meta_data.data_type, [&](auto dummy) { + using T = decltype(dummy); + + threading::parallel_for(selection.index_range(), 512, [&](const IndexRange range) { + for (const int64_t curve_i : selection.slice(range)) { + const IndexRange src_points = src_curves.points_for_curve(curve_i); + + bke::curves::IndexRangeCyclic src_sample_range = get_range_between_endpoints( + start_points[curve_i], end_points[curve_i], {0, src_points.size()}); + sample_interval_linear<T>(attribute.src.template typed<T>().slice(src_points), + attribute.dst.span.typed<T>(), + src_sample_range, + dst_curves.points_for_curve(curve_i), + start_points[curve_i], + end_points[curve_i]); + } + }); + }); + } +} + +static void trim_polygonal_curves(const bke::CurvesGeometry &src_curves, + bke::CurvesGeometry &dst_curves, + const IndexMask selection, + const Span<bke::curves::CurvePoint> start_points, + const Span<bke::curves::CurvePoint> end_points, + MutableSpan<bke::AttributeTransferData> transfer_attributes) +{ + const Span<float3> src_positions = src_curves.positions(); + MutableSpan<float3> dst_positions = dst_curves.positions_for_write(); + + threading::parallel_for(selection.index_range(), 512, [&](const IndexRange range) { + for (const int64_t curve_i : selection.slice(range)) { + const IndexRange src_points = src_curves.points_for_curve(curve_i); + const IndexRange dst_points = dst_curves.points_for_curve(curve_i); + + bke::curves::IndexRangeCyclic src_sample_range = get_range_between_endpoints( + start_points[curve_i], end_points[curve_i], {0, src_points.size()}); + sample_interval_linear<float3>(src_positions.slice(src_points), + dst_positions, + src_sample_range, + dst_points, + start_points[curve_i], + end_points[curve_i]); + } + }); + fill_bezier_data(dst_curves, selection); + fill_nurbs_data(dst_curves, selection); + trim_attribute_linear( + src_curves, dst_curves, selection, start_points, end_points, transfer_attributes); +} + +static void trim_catmull_rom_curves(const bke::CurvesGeometry &src_curves, + bke::CurvesGeometry &dst_curves, + const IndexMask selection, + const Span<bke::curves::CurvePoint> start_points, + const Span<bke::curves::CurvePoint> end_points, + MutableSpan<bke::AttributeTransferData> transfer_attributes) +{ + const Span<float3> src_positions = src_curves.positions(); + const VArray<bool> src_cyclic = src_curves.cyclic(); + MutableSpan<float3> dst_positions = dst_curves.positions_for_write(); + + threading::parallel_for(selection.index_range(), 512, [&](const IndexRange range) { + for (const int64_t curve_i : selection.slice(range)) { + const IndexRange src_points = src_curves.points_for_curve(curve_i); + const IndexRange dst_points = dst_curves.points_for_curve(curve_i); + + bke::curves::IndexRangeCyclic src_sample_range = get_range_between_endpoints( + start_points[curve_i], end_points[curve_i], {0, src_points.size()}); + sample_interval_catmull_rom<float3>(src_positions.slice(src_points), + dst_positions, + src_sample_range, + dst_points, + start_points[curve_i], + end_points[curve_i], + src_cyclic[curve_i]); + } + }); + fill_bezier_data(dst_curves, selection); + fill_nurbs_data(dst_curves, selection); + + for (bke::AttributeTransferData &attribute : transfer_attributes) { + attribute_math::convert_to_static_type(attribute.meta_data.data_type, [&](auto dummy) { + using T = decltype(dummy); + + threading::parallel_for(selection.index_range(), 512, [&](const IndexRange range) { + for (const int64_t curve_i : selection.slice(range)) { + const IndexRange src_points = src_curves.points_for_curve(curve_i); + const IndexRange dst_points = dst_curves.points_for_curve(curve_i); + + bke::curves::IndexRangeCyclic src_sample_range = get_range_between_endpoints( + start_points[curve_i], end_points[curve_i], {0, src_points.size()}); + sample_interval_catmull_rom<T>(attribute.src.template typed<T>().slice(src_points), + attribute.dst.span.typed<T>(), + src_sample_range, + dst_points, + start_points[curve_i], + end_points[curve_i], + src_cyclic[curve_i]); + } + }); + }); + } +} + +static void trim_bezier_curves(const bke::CurvesGeometry &src_curves, + bke::CurvesGeometry &dst_curves, + const IndexMask selection, + const Span<bke::curves::CurvePoint> start_points, + const Span<bke::curves::CurvePoint> end_points, + MutableSpan<bke::AttributeTransferData> transfer_attributes) +{ + const Span<float3> src_positions = src_curves.positions(); + const VArraySpan<int8_t> src_types_l{src_curves.handle_types_left()}; + const VArraySpan<int8_t> src_types_r{src_curves.handle_types_right()}; + const Span<float3> src_handles_l = src_curves.handle_positions_left(); + const Span<float3> src_handles_r = src_curves.handle_positions_right(); + + MutableSpan<float3> dst_positions = dst_curves.positions_for_write(); + MutableSpan<int8_t> dst_types_l = dst_curves.handle_types_left_for_write(); + MutableSpan<int8_t> dst_types_r = dst_curves.handle_types_right_for_write(); + MutableSpan<float3> dst_handles_l = dst_curves.handle_positions_left_for_write(); + MutableSpan<float3> dst_handles_r = dst_curves.handle_positions_right_for_write(); + + threading::parallel_for(selection.index_range(), 512, [&](const IndexRange range) { + for (const int64_t curve_i : selection.slice(range)) { + const IndexRange src_points = src_curves.points_for_curve(curve_i); + const IndexRange dst_points = dst_curves.points_for_curve(curve_i); + + bke::curves::IndexRangeCyclic src_sample_range = get_range_between_endpoints( + start_points[curve_i], end_points[curve_i], {0, src_points.size()}); + sample_interval_bezier(src_positions.slice(src_points), + src_handles_l.slice(src_points), + src_handles_r.slice(src_points), + src_types_l.slice(src_points), + src_types_r.slice(src_points), + dst_positions, + dst_handles_l, + dst_handles_r, + dst_types_l, + dst_types_r, + src_sample_range, + dst_points, + start_points[curve_i], + end_points[curve_i]); + } + }); + fill_nurbs_data(dst_curves, selection); + trim_attribute_linear( + src_curves, dst_curves, selection, start_points, end_points, transfer_attributes); +} + +static void trim_evaluated_curves(const bke::CurvesGeometry &src_curves, + bke::CurvesGeometry &dst_curves, + const IndexMask selection, + const Span<bke::curves::CurvePoint> start_points, + const Span<bke::curves::CurvePoint> end_points, + MutableSpan<bke::AttributeTransferData> transfer_attributes) +{ + const Span<float3> src_eval_positions = src_curves.evaluated_positions(); + MutableSpan<float3> dst_positions = dst_curves.positions_for_write(); + + threading::parallel_for(selection.index_range(), 512, [&](const IndexRange range) { + for (const int64_t curve_i : selection.slice(range)) { + const IndexRange dst_points = dst_curves.points_for_curve(curve_i); + const IndexRange src_evaluated_points = src_curves.evaluated_points_for_curve(curve_i); + + bke::curves::IndexRangeCyclic src_sample_range = get_range_between_endpoints( + start_points[curve_i], end_points[curve_i], {0, src_evaluated_points.size()}); + sample_interval_linear<float3>(src_eval_positions.slice(src_evaluated_points), + dst_positions, + src_sample_range, + dst_points, + start_points[curve_i], + end_points[curve_i]); + } + }); + fill_bezier_data(dst_curves, selection); + fill_nurbs_data(dst_curves, selection); + + for (bke::AttributeTransferData &attribute : transfer_attributes) { + attribute_math::convert_to_static_type(attribute.meta_data.data_type, [&](auto dummy) { + using T = decltype(dummy); + + threading::parallel_for(selection.index_range(), 512, [&](const IndexRange range) { + for (const int64_t curve_i : selection.slice(range)) { + /* Interpolate onto the evaluated point domain and sample the evaluated domain. */ + const IndexRange src_evaluated_points = src_curves.evaluated_points_for_curve(curve_i); + GArray evaluated_data(CPPType::get<T>(), src_evaluated_points.size()); + GMutableSpan evaluated_span = evaluated_data.as_mutable_span(); + src_curves.interpolate_to_evaluated( + curve_i, attribute.src.slice(src_curves.points_for_curve(curve_i)), evaluated_span); + bke::curves::IndexRangeCyclic src_sample_range = get_range_between_endpoints( + start_points[curve_i], end_points[curve_i], {0, src_evaluated_points.size()}); + sample_interval_linear<T>(evaluated_span.typed<T>(), + attribute.dst.span.typed<T>(), + src_sample_range, + dst_curves.points_for_curve(curve_i), + start_points[curve_i], + end_points[curve_i]); + } + }); + }); + } +} + +bke::CurvesGeometry trim_curves(const bke::CurvesGeometry &src_curves, + const IndexMask selection, + const Span<bke::curves::CurvePoint> start_points, + const Span<bke::curves::CurvePoint> end_points) +{ + BLI_assert(selection.size() > 0); + BLI_assert(selection.last() <= start_points.size()); + BLI_assert(start_points.size() == end_points.size()); + + src_curves.ensure_evaluated_offsets(); + Vector<int64_t> inverse_selection_indices; + const IndexMask inverse_selection = selection.invert(src_curves.curves_range(), + inverse_selection_indices); + + /* Create trim curves. */ + bke::CurvesGeometry dst_curves(0, src_curves.curves_num()); + determine_copyable_curve_types(src_curves, + dst_curves, + selection, + inverse_selection, + (CurveTypeMask)(CURVE_TYPE_MASK_CATMULL_ROM | + CURVE_TYPE_MASK_POLY | CURVE_TYPE_MASK_BEZIER)); + + Vector<int64_t> curve_indices; + Vector<int64_t> point_curve_indices; + compute_trim_result_offsets(src_curves, + selection, + inverse_selection, + start_points, + end_points, + dst_curves.curve_types(), + dst_curves.offsets_for_write(), + curve_indices, + point_curve_indices); + /* Finalize by updating the geometry container. */ + dst_curves.resize(dst_curves.offsets().last(), dst_curves.curves_num()); + dst_curves.update_curve_types(); + + /* Populate curve domain. */ + const bke::AttributeAccessor src_attributes = src_curves.attributes(); + bke::MutableAttributeAccessor dst_attributes = dst_curves.attributes_for_write(); + bke::copy_attribute_domain(src_attributes, + dst_attributes, + selection, + ATTR_DOMAIN_CURVE, + {"cyclic", "curve_type", "nurbs_order", "knots_mode"}); + + /* Fetch custom point domain attributes for transfer (copy). */ + Vector<bke::AttributeTransferData> transfer_attributes = bke::retrieve_attributes_for_transfer( + src_attributes, + dst_attributes, + ATTR_DOMAIN_MASK_POINT, + {"position", + "handle_left", + "handle_right", + "handle_type_left", + "handle_type_right", + "nurbs_weight"}); + + auto trim_catmull = [&](IndexMask selection) { + trim_catmull_rom_curves( + src_curves, dst_curves, selection, start_points, end_points, transfer_attributes); + }; + auto trim_poly = [&](IndexMask selection) { + trim_polygonal_curves( + src_curves, dst_curves, selection, start_points, end_points, transfer_attributes); + }; + auto trim_bezier = [&](IndexMask selection) { + trim_bezier_curves( + src_curves, dst_curves, selection, start_points, end_points, transfer_attributes); + }; + auto trim_evaluated = [&](IndexMask selection) { + /* Ensure evaluated positions are available. */ + src_curves.ensure_evaluated_offsets(); + src_curves.evaluated_positions(); + trim_evaluated_curves( + src_curves, dst_curves, selection, start_points, end_points, transfer_attributes); + }; + + auto single_point_catmull = [&](IndexMask selection) { + convert_point_catmull_curves( + src_curves, dst_curves, selection, start_points, transfer_attributes); + }; + auto single_point_poly = [&](IndexMask selection) { + convert_point_polygonal_curves( + src_curves, dst_curves, selection, start_points, transfer_attributes); + }; + auto single_point_bezier = [&](IndexMask selection) { + convert_point_bezier_curves( + src_curves, dst_curves, selection, start_points, transfer_attributes); + }; + auto single_point_evaluated = [&](IndexMask selection) { + convert_point_evaluated_curves( + src_curves, dst_curves, selection, start_points, transfer_attributes); + }; + + /* Populate point domain. */ + bke::curves::foreach_curve_by_type(src_curves.curve_types(), + src_curves.curve_type_counts(), + curve_indices.as_span(), + trim_catmull, + trim_poly, + trim_bezier, + trim_evaluated); + + if (point_curve_indices.size()) { + bke::curves::foreach_curve_by_type(src_curves.curve_types(), + src_curves.curve_type_counts(), + point_curve_indices.as_span(), + single_point_catmull, + single_point_poly, + single_point_bezier, + single_point_evaluated); + } + /* Cleanup/close context */ + for (bke::AttributeTransferData &attribute : transfer_attributes) { + attribute.dst.finish(); + } + + /* Copy unselected */ + if (!inverse_selection.is_empty()) { + bke::copy_attribute_domain( + src_attributes, dst_attributes, inverse_selection, ATTR_DOMAIN_CURVE); + /* Trim curves are no longer cyclic. If all curves are trimmed, this will be set implicitly. */ + dst_curves.cyclic_for_write().fill_indices(selection, false); + + /* Copy point domain. */ + for (auto &attribute : bke::retrieve_attributes_for_transfer( + src_attributes, dst_attributes, ATTR_DOMAIN_MASK_POINT)) { + bke::curves::copy_point_data( + src_curves, dst_curves, inverse_selection, attribute.src, attribute.dst.span); + attribute.dst.finish(); + } + } + + dst_curves.tag_topology_changed(); + return dst_curves; +} + +} // namespace blender::geometry diff --git a/source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc b/source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc index 443f67be421..0d3ae47e712 100644 --- a/source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc +++ b/source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc @@ -9,12 +9,12 @@ #include "NOD_socket_search_link.hh" +#include "GEO_trim_curves.hh" + #include "node_geometry_util.hh" namespace blender::nodes::node_geo_curve_trim_cc { -using blender::attribute_math::mix2; - NODE_STORAGE_FUNCS(NodeGeometryCurveTrim) static void node_declare(NodeDeclarationBuilder &b) @@ -108,394 +108,6 @@ static void node_gather_link_searches(GatherLinkSearchOpParams ¶ms) } } -struct TrimLocation { - /* Control point index at the start side of the trim location. */ - int left_index; - /* Control point index at the end of the trim location's segment. */ - int right_index; - /* The factor between the left and right indices. */ - float factor; -}; - -template<typename T> -static void shift_slice_to_start(MutableSpan<T> data, const int start_index, const int num) -{ - BLI_assert(start_index + num - 1 <= data.size()); - memmove(data.data(), &data[start_index], sizeof(T) * num); -} - -/* Shift slice to start of span and modifies start and end data. */ -template<typename T> -static void linear_trim_data(const TrimLocation &start, - const TrimLocation &end, - MutableSpan<T> data) -{ - const int num = end.right_index - start.left_index + 1; - - if (start.left_index > 0) { - shift_slice_to_start<T>(data, start.left_index, num); - } - - const T start_data = mix2<T>(start.factor, data.first(), data[1]); - const T end_data = mix2<T>(end.factor, data[num - 2], data[num - 1]); - - data.first() = start_data; - data[num - 1] = end_data; -} - -/** - * Identical operation as #linear_trim_data, but copy data to a new #MutableSpan rather than - * modifying the original data. - */ -template<typename T> -static void linear_trim_to_output_data(const TrimLocation &start, - const TrimLocation &end, - Span<T> src, - MutableSpan<T> dst) -{ - const int num = end.right_index - start.left_index + 1; - - const T start_data = mix2<T>(start.factor, src[start.left_index], src[start.right_index]); - const T end_data = mix2<T>(end.factor, src[end.left_index], src[end.right_index]); - - dst.copy_from(src.slice(start.left_index, num)); - dst.first() = start_data; - dst.last() = end_data; -} - -/* Look up the control points to the left and right of factor, and get the factor between them. */ -static TrimLocation lookup_control_point_position(const Spline::LookupResult &lookup, - const BezierSpline &spline) -{ - Span<int> offsets = spline.control_point_offsets(); - - const int *offset = std::lower_bound(offsets.begin(), offsets.end(), lookup.evaluated_index); - const int index = offset - offsets.begin(); - - const int left = offsets[index] > lookup.evaluated_index ? index - 1 : index; - const int right = left == (spline.size() - 1) ? 0 : left + 1; - - const float offset_in_segment = lookup.evaluated_index + lookup.factor - offsets[left]; - const int segment_eval_num = offsets[left + 1] - offsets[left]; - const float factor = std::clamp(offset_in_segment / segment_eval_num, 0.0f, 1.0f); - - return {left, right, factor}; -} - -static void trim_poly_spline(Spline &spline, - const Spline::LookupResult &start_lookup, - const Spline::LookupResult &end_lookup) -{ - /* Poly splines have a 1 to 1 mapping between control points and evaluated points. */ - const TrimLocation start = { - start_lookup.evaluated_index, start_lookup.next_evaluated_index, start_lookup.factor}; - const TrimLocation end = { - end_lookup.evaluated_index, end_lookup.next_evaluated_index, end_lookup.factor}; - - const int num = end.right_index - start.left_index + 1; - - linear_trim_data<float3>(start, end, spline.positions()); - linear_trim_data<float>(start, end, spline.radii()); - linear_trim_data<float>(start, end, spline.tilts()); - - spline.attributes.foreach_attribute( - [&](const AttributeIDRef &attribute_id, const AttributeMetaData &UNUSED(meta_data)) { - std::optional<GMutableSpan> src = spline.attributes.get_for_write(attribute_id); - BLI_assert(src); - attribute_math::convert_to_static_type(src->type(), [&](auto dummy) { - using T = decltype(dummy); - linear_trim_data<T>(start, end, src->typed<T>()); - }); - return true; - }, - ATTR_DOMAIN_POINT); - - spline.resize(num); -} - -/** - * Trim NURB splines by converting to a poly spline. - */ -static PolySpline trim_nurbs_spline(const Spline &spline, - const Spline::LookupResult &start_lookup, - const Spline::LookupResult &end_lookup) -{ - /* Since this outputs a poly spline, the evaluated indices are the control point indices. */ - const TrimLocation start = { - start_lookup.evaluated_index, start_lookup.next_evaluated_index, start_lookup.factor}; - const TrimLocation end = { - end_lookup.evaluated_index, end_lookup.next_evaluated_index, end_lookup.factor}; - - const int num = end.right_index - start.left_index + 1; - - /* Create poly spline and copy trimmed data to it. */ - PolySpline new_spline; - new_spline.resize(num); - - /* Copy generic attribute data. */ - spline.attributes.foreach_attribute( - [&](const AttributeIDRef &attribute_id, const AttributeMetaData &meta_data) { - std::optional<GSpan> src = spline.attributes.get_for_read(attribute_id); - BLI_assert(src); - if (!new_spline.attributes.create(attribute_id, meta_data.data_type)) { - BLI_assert_unreachable(); - return false; - } - std::optional<GMutableSpan> dst = new_spline.attributes.get_for_write(attribute_id); - BLI_assert(dst); - - attribute_math::convert_to_static_type(src->type(), [&](auto dummy) { - using T = decltype(dummy); - VArray<T> eval_data = spline.interpolate_to_evaluated<T>(src->typed<T>()); - linear_trim_to_output_data<T>( - start, end, eval_data.get_internal_span(), dst->typed<T>()); - }); - return true; - }, - ATTR_DOMAIN_POINT); - - linear_trim_to_output_data<float3>( - start, end, spline.evaluated_positions(), new_spline.positions()); - - VArray<float> evaluated_radii = spline.interpolate_to_evaluated(spline.radii()); - linear_trim_to_output_data<float>( - start, end, evaluated_radii.get_internal_span(), new_spline.radii()); - - VArray<float> evaluated_tilts = spline.interpolate_to_evaluated(spline.tilts()); - linear_trim_to_output_data<float>( - start, end, evaluated_tilts.get_internal_span(), new_spline.tilts()); - - return new_spline; -} - -/** - * Trim Bezier splines by adjusting the first and last handles - * and control points to maintain the original shape. - */ -static void trim_bezier_spline(Spline &spline, - const Spline::LookupResult &start_lookup, - const Spline::LookupResult &end_lookup) -{ - BezierSpline &bezier_spline = static_cast<BezierSpline &>(spline); - - const TrimLocation start = lookup_control_point_position(start_lookup, bezier_spline); - TrimLocation end = lookup_control_point_position(end_lookup, bezier_spline); - - const Span<int> control_offsets = bezier_spline.control_point_offsets(); - - /* The number of control points in the resulting spline. */ - const int num = end.right_index - start.left_index + 1; - - /* Trim the spline attributes. Done before end.factor recalculation as it needs - * the original end.factor value. */ - linear_trim_data<float>(start, end, bezier_spline.radii()); - linear_trim_data<float>(start, end, bezier_spline.tilts()); - spline.attributes.foreach_attribute( - [&](const AttributeIDRef &attribute_id, const AttributeMetaData &UNUSED(meta_data)) { - std::optional<GMutableSpan> src = spline.attributes.get_for_write(attribute_id); - BLI_assert(src); - attribute_math::convert_to_static_type(src->type(), [&](auto dummy) { - using T = decltype(dummy); - linear_trim_data<T>(start, end, src->typed<T>()); - }); - return true; - }, - ATTR_DOMAIN_POINT); - - /* Recalculate end.factor if the `num` is two, because the adjustment in the - * position of the control point of the spline to the left of the new end point will change the - * factor between them. */ - if (num == 2) { - if (start_lookup.factor == 1.0f) { - end.factor = 0.0f; - } - else { - end.factor = (end_lookup.evaluated_index + end_lookup.factor - - (start_lookup.evaluated_index + start_lookup.factor)) / - (control_offsets[end.right_index] - - (start_lookup.evaluated_index + start_lookup.factor)); - end.factor = std::clamp(end.factor, 0.0f, 1.0f); - } - } - - BezierSpline::InsertResult start_point = bezier_spline.calculate_segment_insertion( - start.left_index, start.right_index, start.factor); - - /* Update the start control point parameters so they are used calculating the new end point. */ - bezier_spline.positions()[start.left_index] = start_point.position; - bezier_spline.handle_positions_right()[start.left_index] = start_point.right_handle; - bezier_spline.handle_positions_left()[start.right_index] = start_point.handle_next; - - const BezierSpline::InsertResult end_point = bezier_spline.calculate_segment_insertion( - end.left_index, end.right_index, end.factor); - - /* If `num` is two, then the start point right handle needs to change to reflect the end point - * previous handle update. */ - if (num == 2) { - start_point.right_handle = end_point.handle_prev; - } - - /* Shift control point position data to start at beginning of array. */ - if (start.left_index > 0) { - shift_slice_to_start(bezier_spline.positions(), start.left_index, num); - shift_slice_to_start(bezier_spline.handle_positions_left(), start.left_index, num); - shift_slice_to_start(bezier_spline.handle_positions_right(), start.left_index, num); - } - - bezier_spline.positions().first() = start_point.position; - bezier_spline.positions()[num - 1] = end_point.position; - - bezier_spline.handle_positions_left().first() = start_point.left_handle; - bezier_spline.handle_positions_left()[num - 1] = end_point.left_handle; - - bezier_spline.handle_positions_right().first() = start_point.right_handle; - bezier_spline.handle_positions_right()[num - 1] = end_point.right_handle; - - /* If there is at least one control point between the endpoints, update the control - * point handle to the right of the start point and to the left of the end point. */ - if (num > 2) { - bezier_spline.handle_positions_left()[start.right_index - start.left_index] = - start_point.handle_next; - bezier_spline.handle_positions_right()[end.left_index - start.left_index] = - end_point.handle_prev; - } - - bezier_spline.resize(num); -} - -static void trim_spline(SplinePtr &spline, - const Spline::LookupResult start, - const Spline::LookupResult end) -{ - switch (spline->type()) { - case CURVE_TYPE_BEZIER: - trim_bezier_spline(*spline, start, end); - break; - case CURVE_TYPE_POLY: - trim_poly_spline(*spline, start, end); - break; - case CURVE_TYPE_NURBS: - spline = std::make_unique<PolySpline>(trim_nurbs_spline(*spline, start, end)); - break; - case CURVE_TYPE_CATMULL_ROM: - BLI_assert_unreachable(); - spline = {}; - } - spline->mark_cache_invalid(); -} - -template<typename T> -static void to_single_point_data(const TrimLocation &trim, MutableSpan<T> data) -{ - data.first() = mix2<T>(trim.factor, data[trim.left_index], data[trim.right_index]); -} -template<typename T> -static void to_single_point_data(const TrimLocation &trim, Span<T> src, MutableSpan<T> dst) -{ - dst.first() = mix2<T>(trim.factor, src[trim.left_index], src[trim.right_index]); -} - -static void to_single_point_bezier(Spline &spline, const Spline::LookupResult &lookup) -{ - BezierSpline &bezier = static_cast<BezierSpline &>(spline); - - const TrimLocation trim = lookup_control_point_position(lookup, bezier); - - const BezierSpline::InsertResult new_point = bezier.calculate_segment_insertion( - trim.left_index, trim.right_index, trim.factor); - bezier.positions().first() = new_point.position; - bezier.handle_types_left().first() = BEZIER_HANDLE_FREE; - bezier.handle_types_right().first() = BEZIER_HANDLE_FREE; - bezier.handle_positions_left().first() = new_point.left_handle; - bezier.handle_positions_right().first() = new_point.right_handle; - - to_single_point_data<float>(trim, bezier.radii()); - to_single_point_data<float>(trim, bezier.tilts()); - spline.attributes.foreach_attribute( - [&](const AttributeIDRef &attribute_id, const AttributeMetaData &UNUSED(meta_data)) { - std::optional<GMutableSpan> data = spline.attributes.get_for_write(attribute_id); - attribute_math::convert_to_static_type(data->type(), [&](auto dummy) { - using T = decltype(dummy); - to_single_point_data<T>(trim, data->typed<T>()); - }); - return true; - }, - ATTR_DOMAIN_POINT); - spline.resize(1); -} - -static void to_single_point_poly(Spline &spline, const Spline::LookupResult &lookup) -{ - const TrimLocation trim{lookup.evaluated_index, lookup.next_evaluated_index, lookup.factor}; - - to_single_point_data<float3>(trim, spline.positions()); - to_single_point_data<float>(trim, spline.radii()); - to_single_point_data<float>(trim, spline.tilts()); - spline.attributes.foreach_attribute( - [&](const AttributeIDRef &attribute_id, const AttributeMetaData &UNUSED(meta_data)) { - std::optional<GMutableSpan> data = spline.attributes.get_for_write(attribute_id); - attribute_math::convert_to_static_type(data->type(), [&](auto dummy) { - using T = decltype(dummy); - to_single_point_data<T>(trim, data->typed<T>()); - }); - return true; - }, - ATTR_DOMAIN_POINT); - spline.resize(1); -} - -static PolySpline to_single_point_nurbs(const Spline &spline, const Spline::LookupResult &lookup) -{ - /* Since this outputs a poly spline, the evaluated indices are the control point indices. */ - const TrimLocation trim{lookup.evaluated_index, lookup.next_evaluated_index, lookup.factor}; - - /* Create poly spline and copy trimmed data to it. */ - PolySpline new_spline; - new_spline.resize(1); - - spline.attributes.foreach_attribute( - [&](const AttributeIDRef &attribute_id, const AttributeMetaData &meta_data) { - new_spline.attributes.create(attribute_id, meta_data.data_type); - std::optional<GSpan> src = spline.attributes.get_for_read(attribute_id); - std::optional<GMutableSpan> dst = new_spline.attributes.get_for_write(attribute_id); - attribute_math::convert_to_static_type(src->type(), [&](auto dummy) { - using T = decltype(dummy); - VArray<T> eval_data = spline.interpolate_to_evaluated<T>(src->typed<T>()); - to_single_point_data<T>(trim, eval_data.get_internal_span(), dst->typed<T>()); - }); - return true; - }, - ATTR_DOMAIN_POINT); - - to_single_point_data<float3>(trim, spline.evaluated_positions(), new_spline.positions()); - - VArray<float> evaluated_radii = spline.interpolate_to_evaluated(spline.radii()); - to_single_point_data<float>(trim, evaluated_radii.get_internal_span(), new_spline.radii()); - - VArray<float> evaluated_tilts = spline.interpolate_to_evaluated(spline.tilts()); - to_single_point_data<float>(trim, evaluated_tilts.get_internal_span(), new_spline.tilts()); - - return new_spline; -} - -static void to_single_point_spline(SplinePtr &spline, const Spline::LookupResult &lookup) -{ - switch (spline->type()) { - case CURVE_TYPE_BEZIER: - to_single_point_bezier(*spline, lookup); - break; - case CURVE_TYPE_POLY: - to_single_point_poly(*spline, lookup); - break; - case CURVE_TYPE_NURBS: - spline = std::make_unique<PolySpline>(to_single_point_nurbs(*spline, lookup)); - break; - case CURVE_TYPE_CATMULL_ROM: - BLI_assert_unreachable(); - spline = {}; - } -} - static void geometry_set_curve_trim(GeometrySet &geometry_set, const GeometryNodeCurveSampleMode mode, Field<float> &start_field, @@ -505,68 +117,49 @@ static void geometry_set_curve_trim(GeometrySet &geometry_set, return; } const Curves &src_curves_id = *geometry_set.get_curves_for_read(); - const bke::CurvesGeometry &curves = bke::CurvesGeometry::wrap(src_curves_id.geometry); + const bke::CurvesGeometry &src_curves = bke::CurvesGeometry::wrap(src_curves_id.geometry); + if (src_curves.curves_num() == 0) { + return; + } - bke::CurvesFieldContext field_context{curves, ATTR_DOMAIN_CURVE}; - fn::FieldEvaluator evaluator{field_context, curves.curves_num()}; + bke::CurvesFieldContext field_context{src_curves, ATTR_DOMAIN_CURVE}; + fn::FieldEvaluator evaluator{field_context, src_curves.curves_num()}; evaluator.add(start_field); evaluator.add(end_field); evaluator.evaluate(); const VArray<float> starts = evaluator.get_evaluated<float>(0); const VArray<float> ends = evaluator.get_evaluated<float>(1); - std::unique_ptr<CurveEval> curve = curves_to_curve_eval(src_curves_id); - MutableSpan<SplinePtr> splines = curve->splines(); - - threading::parallel_for(splines.index_range(), 128, [&](IndexRange range) { - for (const int i : range) { - SplinePtr &spline = splines[i]; - - /* Currently trimming cyclic splines is not supported. It could be in the future though. */ - if (spline->is_cyclic()) { - continue; - } - - if (spline->evaluated_edges_num() == 0) { - continue; - } - - const float length = spline->length(); - if (length == 0.0f) { - continue; - } - - const float start = starts[i]; - const float end = ends[i]; - - /* When the start and end samples are reversed, instead of implicitly reversing the spline - * or switching the parameters, create a single point spline with the end sample point. */ - if (end <= start) { - if (mode == GEO_NODE_CURVE_SAMPLE_LENGTH) { - to_single_point_spline(spline, - spline->lookup_evaluated_length(std::clamp(start, 0.0f, length))); - } - else { - to_single_point_spline(spline, - spline->lookup_evaluated_factor(std::clamp(start, 0.0f, 1.0f))); - } - continue; - } - - if (mode == GEO_NODE_CURVE_SAMPLE_LENGTH) { - trim_spline(spline, - spline->lookup_evaluated_length(std::clamp(start, 0.0f, length)), - spline->lookup_evaluated_length(std::clamp(end, 0.0f, length))); - } - else { - trim_spline(spline, - spline->lookup_evaluated_factor(std::clamp(start, 0.0f, 1.0f)), - spline->lookup_evaluated_factor(std::clamp(end, 0.0f, 1.0f))); - } + const VArray<bool> cyclic = src_curves.cyclic(); + + /* If node length input is on form [0, 1] instead of [0, length]*/ + const bool normalized_length_lookup = mode == GEO_NODE_CURVE_SAMPLE_FACTOR; + + /* Stack start + end field. */ + Vector<float> length_factors(src_curves.curves_num() * 2); + Vector<int64_t> lookup_indices(src_curves.curves_num() * 2); + threading::parallel_for(src_curves.curves_range(), 512, [&](IndexRange curve_range) { + for (const int64_t curve_i : curve_range) { + const bool negative_trim = !cyclic[curve_i] && starts[curve_i] > ends[curve_i]; + length_factors[curve_i] = starts[curve_i]; + length_factors[curve_i + src_curves.curves_num()] = negative_trim ? starts[curve_i] : + ends[curve_i]; + lookup_indices[curve_i] = curve_i; + lookup_indices[curve_i + src_curves.curves_num()] = curve_i; } }); - Curves *dst_curves_id = curve_eval_to_curves(*curve); + /* Create curve trim lookup table. */ + Array<bke::curves::CurvePoint, 12> point_lookups = geometry::lookup_curve_points( + src_curves, length_factors, lookup_indices, normalized_length_lookup); + + bke::CurvesGeometry dst_curves = geometry::trim_curves( + src_curves, + src_curves.curves_range().as_span(), + point_lookups.as_span().slice(0, src_curves.curves_num()), + point_lookups.as_span().slice(src_curves.curves_num(), src_curves.curves_num())); + + Curves *dst_curves_id = bke::curves_new_nomain(std::move(dst_curves)); bke::curves_copy_parameters(src_curves_id, *dst_curves_id); geometry_set.replace_curves(dst_curves_id); } |