diff options
| -rw-r--r-- | source/blender/blenkernel/BKE_curves.hh | 50 | ||||
| -rw-r--r-- | source/blender/blenkernel/intern/curve_bezier.cc | 27 | ||||
| -rw-r--r-- | source/blender/blenkernel/intern/curve_catmull_rom.cc | 101 | ||||
| -rw-r--r-- | source/blender/blenlib/BLI_index_range.hh | 19 | ||||
| -rw-r--r-- | source/blender/geometry/CMakeLists.txt | 2 | ||||
| -rw-r--r-- | source/blender/geometry/GEO_subdivide_curves.hh | 26 | ||||
| -rw-r--r-- | source/blender/geometry/intern/subdivide_curves.cc | 486 | ||||
| -rw-r--r-- | source/blender/nodes/geometry/nodes/node_geo_curve_subdivide.cc | 319 |
8 files changed, 687 insertions, 343 deletions
diff --git a/source/blender/blenkernel/BKE_curves.hh b/source/blender/blenkernel/BKE_curves.hh index 767936e2a26..3e00dc78b74 100644 --- a/source/blender/blenkernel/BKE_curves.hh +++ b/source/blender/blenkernel/BKE_curves.hh @@ -483,6 +483,8 @@ namespace bezier { * Return true if the handles that make up a segment both have a vector type. Vector segments for * Bezier curves have special behavior because they aren't divided into many evaluated points. */ +bool segment_is_vector(const HandleType left, const HandleType right); +bool segment_is_vector(const int8_t left, const int8_t right); bool segment_is_vector(Span<int8_t> handle_types_left, Span<int8_t> handle_types_right, int segment_index); @@ -515,6 +517,35 @@ void calculate_evaluated_offsets(Span<int8_t> handle_types_left, int resolution, MutableSpan<int> evaluated_offsets); +/** See #insert. */ +struct Insertion { + float3 handle_prev; + float3 left_handle; + float3 position; + float3 right_handle; + float3 handle_next; +}; + +/** + * Compute the Bezier segment insertion for the given parameter on the segment, returning + * the position and handles of the new point and the updated existing handle positions. + * <pre> + * handle_prev handle_next + * x-----------------x + * / \ + * / x---O---x \ + * / result \ + * / \ + * O O + * point_prev point_next + * </pre> + */ +Insertion insert(const float3 &point_prev, + const float3 &handle_prev, + const float3 &handle_next, + const float3 &point_next, + float parameter); + /** * Calculate the automatically defined positions for a vector handle (#BEZIER_HANDLE_VECTOR). While * this can be calculated automatically with #calculate_auto_handles, when more context is @@ -607,6 +638,15 @@ int calculate_evaluated_num(int points_num, bool cyclic, int resolution); */ void interpolate_to_evaluated(GSpan src, bool cyclic, int resolution, GMutableSpan dst); +/** + * Evaluate the Catmull Rom curve. The size of each segment and its offset in the #dst span + * is encoded in #evaluated_offsets, with the same method as #CurvesGeometry::offsets(). + */ +void interpolate_to_evaluated(const GSpan src, + const bool cyclic, + const Span<int> evaluated_offsets, + GMutableSpan dst); + } // namespace catmull_rom /** \} */ @@ -827,6 +867,16 @@ inline bool point_is_sharp(const Span<int8_t> handle_types_left, ELEM(handle_types_right[index], BEZIER_HANDLE_VECTOR, BEZIER_HANDLE_FREE); } +inline bool segment_is_vector(const HandleType left, const HandleType right) +{ + return left == BEZIER_HANDLE_VECTOR && right == BEZIER_HANDLE_VECTOR; +} + +inline bool segment_is_vector(const int8_t left, const int8_t right) +{ + return segment_is_vector(HandleType(left), HandleType(right)); +} + inline float3 calculate_vector_handle(const float3 &point, const float3 &next_point) { return math::interpolate(point, next_point, 1.0f / 3.0f); diff --git a/source/blender/blenkernel/intern/curve_bezier.cc b/source/blender/blenkernel/intern/curve_bezier.cc index 1d6ee4938b5..59b09384698 100644 --- a/source/blender/blenkernel/intern/curve_bezier.cc +++ b/source/blender/blenkernel/intern/curve_bezier.cc @@ -16,15 +16,14 @@ bool segment_is_vector(const Span<int8_t> handle_types_left, const int segment_index) { BLI_assert(handle_types_left.index_range().drop_back(1).contains(segment_index)); - return handle_types_right[segment_index] == BEZIER_HANDLE_VECTOR && - handle_types_left[segment_index + 1] == BEZIER_HANDLE_VECTOR; + return segment_is_vector(handle_types_right[segment_index], + handle_types_left[segment_index + 1]); } bool last_cyclic_segment_is_vector(const Span<int8_t> handle_types_left, const Span<int8_t> handle_types_right) { - return handle_types_right.last() == BEZIER_HANDLE_VECTOR && - handle_types_left.first() == BEZIER_HANDLE_VECTOR; + return segment_is_vector(handle_types_right.last(), handle_types_left.first()); } void calculate_evaluated_offsets(const Span<int8_t> handle_types_left, @@ -59,6 +58,26 @@ void calculate_evaluated_offsets(const Span<int8_t> handle_types_left, evaluated_offsets.last() = offset; } +Insertion insert(const float3 &point_prev, + const float3 &handle_prev, + const float3 &handle_next, + const float3 &point_next, + float parameter) +{ + /* De Casteljau Bezier subdivision. */ + BLI_assert(parameter <= 1.0f && parameter >= 0.0f); + + const float3 center_point = math::interpolate(handle_prev, handle_next, parameter); + + Insertion result; + result.handle_prev = math::interpolate(point_prev, handle_prev, parameter); + result.handle_next = math::interpolate(handle_next, point_next, parameter); + result.left_handle = math::interpolate(result.handle_prev, center_point, parameter); + result.right_handle = math::interpolate(center_point, result.handle_next, parameter); + result.position = math::interpolate(result.left_handle, result.right_handle, parameter); + return result; +} + static float3 calculate_aligned_handle(const float3 &position, const float3 &other_handle, const float3 &aligned_handle) diff --git a/source/blender/blenkernel/intern/curve_catmull_rom.cc b/source/blender/blenkernel/intern/curve_catmull_rom.cc index 1875c7b366a..952d59edcf9 100644 --- a/source/blender/blenkernel/intern/curve_catmull_rom.cc +++ b/source/blender/blenkernel/intern/curve_catmull_rom.cc @@ -39,15 +39,18 @@ static void evaluate_segment(const T &a, const T &b, const T &c, const T &d, Mut } } -template<typename T> +/** + * \param range_fn: Returns an index range describing where in the #dst span each segment should be + * evaluated to, and how many points to add to it. This is used to avoid the need to allocate an + * actual offsets array in typical evaluation use cases where the resolution is per-curve. + */ +template<typename T, typename RangeForSegmentFn> static void interpolate_to_evaluated(const Span<T> src, const bool cyclic, - const int resolution, + const RangeForSegmentFn &range_fn, MutableSpan<T> dst) { - BLI_assert(dst.size() == calculate_evaluated_num(src.size(), cyclic, resolution)); - /* - First deal with one and two point curves need special attention. * - Then evaluate the first and last segment(s) whose control points need to wrap around * to the other side of the source array. @@ -57,11 +60,14 @@ static void interpolate_to_evaluated(const Span<T> src, dst.first() = src.first(); return; } + + const IndexRange first = range_fn(0); + if (src.size() == 2) { - evaluate_segment(src.first(), src.first(), src.last(), src.last(), dst.take_front(resolution)); + evaluate_segment(src.first(), src.first(), src.last(), src.last(), dst.slice(first)); if (cyclic) { - evaluate_segment( - src.last(), src.last(), src.first(), src.first(), dst.take_back(resolution)); + const IndexRange last = range_fn(1); + evaluate_segment(src.last(), src.last(), src.first(), src.first(), dst.slice(last)); } else { dst.last() = src.last(); @@ -69,39 +75,65 @@ static void interpolate_to_evaluated(const Span<T> src, return; } + const IndexRange second_to_last = range_fn(src.index_range().last(1)); + const IndexRange last = range_fn(src.index_range().last()); if (cyclic) { - /* The first segment. */ - evaluate_segment(src.last(), src[0], src[1], src[2], dst.take_front(resolution)); - /* The second-to-last segment. */ - evaluate_segment(src.last(2), - src.last(1), - src.last(), - src.first(), - dst.take_back(resolution * 2).drop_back(resolution)); - /* The last segment. */ - evaluate_segment(src.last(1), src.last(), src[0], src[1], dst.take_back(resolution)); + evaluate_segment(src.last(), src[0], src[1], src[2], dst.slice(first)); + evaluate_segment(src.last(2), src.last(1), src.last(), src.first(), dst.slice(second_to_last)); + evaluate_segment(src.last(1), src.last(), src[0], src[1], dst.slice(last)); } else { - /* The first segment. */ - evaluate_segment(src[0], src[0], src[1], src[2], dst.take_front(resolution)); - /* The last segment. */ - evaluate_segment( - src.last(2), src.last(1), src.last(), src.last(), dst.drop_back(1).take_back(resolution)); - /* The final point of the last segment. */ + evaluate_segment(src[0], src[0], src[1], src[2], dst.slice(first)); + evaluate_segment(src.last(2), src.last(1), src.last(), src.last(), dst.slice(second_to_last)); + /* For non-cyclic curves, the last segment should always just have a single point. We could + * assert that the size of the provided range is 1 here, but that would require specializing + * the #range_fn implementation for the last point, which may have a performance cost. */ dst.last() = src.last(); } /* Evaluate every segment that isn't the first or last. */ - const int grain_size = std::max(512 / resolution, 1); const IndexRange inner_range = src.index_range().drop_back(2).drop_front(1); - threading::parallel_for(inner_range, grain_size, [&](IndexRange range) { + threading::parallel_for(inner_range, 512, [&](IndexRange range) { for (const int i : range) { - const IndexRange segment_range(resolution * i, resolution); - evaluate_segment(src[i - 1], src[i], src[i + 1], src[i + 2], dst.slice(segment_range)); + const IndexRange segment = range_fn(i); + evaluate_segment(src[i - 1], src[i], src[i + 1], src[i + 2], dst.slice(segment)); } }); } +template<typename T> +static void interpolate_to_evaluated(const Span<T> src, + const bool cyclic, + const int resolution, + MutableSpan<T> dst) + +{ + BLI_assert(dst.size() == calculate_evaluated_num(src.size(), cyclic, resolution)); + interpolate_to_evaluated( + src, + cyclic, + [resolution](const int segment_i) -> IndexRange { + return {segment_i * resolution, resolution}; + }, + dst); +} + +template<typename T> +static void interpolate_to_evaluated(const Span<T> src, + const bool cyclic, + const Span<int> evaluated_offsets, + MutableSpan<T> dst) + +{ + interpolate_to_evaluated( + src, + cyclic, + [evaluated_offsets](const int segment_i) -> IndexRange { + return bke::offsets_to_range(evaluated_offsets, segment_i); + }, + dst); +} + void interpolate_to_evaluated(const GSpan src, const bool cyclic, const int resolution, @@ -117,4 +149,19 @@ void interpolate_to_evaluated(const GSpan src, }); } +void interpolate_to_evaluated(const GSpan src, + const bool cyclic, + const Span<int> evaluated_offsets, + GMutableSpan dst) +{ + attribute_math::convert_to_static_type(src.type(), [&](auto dummy) { + using T = decltype(dummy); + /* 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>) { + interpolate_to_evaluated(src.typed<T>(), cyclic, evaluated_offsets, dst.typed<T>()); + } + }); +} + } // namespace blender::bke::curves::catmull_rom diff --git a/source/blender/blenlib/BLI_index_range.hh b/source/blender/blenlib/BLI_index_range.hh index 7d5c2400bba..bd0a7e5bb7a 100644 --- a/source/blender/blenlib/BLI_index_range.hh +++ b/source/blender/blenlib/BLI_index_range.hh @@ -186,13 +186,15 @@ class IndexRange { } /** - * Get the last element in the range. - * Asserts when the range is empty. + * Get the nth last element in the range. + * Asserts when the range is empty or when n is negative. */ - constexpr int64_t last() const + constexpr int64_t last(const int64_t n = 0) const { + BLI_assert(n >= 0); + BLI_assert(n < size_); BLI_assert(this->size() > 0); - return start_ + size_ - 1; + return start_ + size_ - 1 - n; } /** @@ -280,6 +282,15 @@ class IndexRange { } /** + * Move the range forward or backward within the larger array. The amount may be negative, + * but its absolute value cannot be greater than the existing start of the range. + */ + constexpr IndexRange shift(int64_t n) const + { + return IndexRange(start_ + n, size_); + } + + /** * Get read-only access to a memory buffer that contains the range as actual numbers. */ Span<int64_t> as_span() const; diff --git a/source/blender/geometry/CMakeLists.txt b/source/blender/geometry/CMakeLists.txt index 21b2071d0e6..df66a806c16 100644 --- a/source/blender/geometry/CMakeLists.txt +++ b/source/blender/geometry/CMakeLists.txt @@ -25,6 +25,7 @@ set(SRC intern/resample_curves.cc intern/reverse_uv_sampler.cc intern/set_curve_type.cc + intern/subdivide_curves.cc intern/uv_parametrizer.c GEO_add_curves_on_mesh.hh @@ -37,6 +38,7 @@ set(SRC GEO_resample_curves.hh GEO_reverse_uv_sampler.hh GEO_set_curve_type.hh + GEO_subdivide_curves.hh GEO_uv_parametrizer.h ) diff --git a/source/blender/geometry/GEO_subdivide_curves.hh b/source/blender/geometry/GEO_subdivide_curves.hh new file mode 100644 index 00000000000..4f671467b24 --- /dev/null +++ b/source/blender/geometry/GEO_subdivide_curves.hh @@ -0,0 +1,26 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ + +#pragma once + +#include "BLI_function_ref.hh" +#include "BLI_index_mask.hh" + +#include "BKE_curves.hh" + +struct CurveComponent; + +namespace blender::geometry { + +/** + * Add more points along each segment, with the amount of points to add in each segment described + * by the #cuts input. The new points are equidistant in parameter space, but not in the actual + * distances. + * + * \param selection: A selection of curves to consider when subdividing. + */ +Curves *subdivide_curves(const CurveComponent &src_component, + const bke::CurvesGeometry &src_curves, + IndexMask selection, + const VArray<int> &cuts); + +} // namespace blender::geometry diff --git a/source/blender/geometry/intern/subdivide_curves.cc b/source/blender/geometry/intern/subdivide_curves.cc new file mode 100644 index 00000000000..4fb21e53013 --- /dev/null +++ b/source/blender/geometry/intern/subdivide_curves.cc @@ -0,0 +1,486 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ + +#include "BKE_attribute_math.hh" +#include "BKE_curves.hh" +#include "BKE_curves_utils.hh" +#include "BKE_geometry_set.hh" + +#include "BLI_task.hh" + +#include "GEO_subdivide_curves.hh" + +namespace blender::geometry { + +/** + * \warning Only the curve domain of the input is copied, so the result is invalid! + */ +static Curves *create_result_curves(const bke::CurvesGeometry &src_curves) +{ + Curves *dst_curves_id = bke::curves_new_nomain(0, src_curves.curves_num()); + bke::CurvesGeometry &dst_curves = bke::CurvesGeometry::wrap(dst_curves_id->geometry); + CurveComponent dst_component; + dst_component.replace(dst_curves_id, GeometryOwnershipType::Editable); + /* Directly copy curve attributes, since they stay the same. */ + CustomData_copy(&src_curves.curve_data, + &dst_curves.curve_data, + CD_MASK_ALL, + CD_DUPLICATE, + src_curves.curves_num()); + dst_curves.runtime->type_counts = src_curves.runtime->type_counts; + + return dst_curves_id; +} + +/** + * Return a range used to retrieve values from an array of values stored per point, but with an + * extra element at the end of each curve. This is useful for offsets within curves, where it is + * convenient to store the first 0 and have the last offset be the total result curve size. + */ +static IndexRange curve_dst_offsets(const IndexRange points, const int curve_index) +{ + return {curve_index + points.start(), points.size() + 1}; +} + +static void calculate_result_offsets(const bke::CurvesGeometry &src_curves, + const IndexMask selection, + const Span<IndexRange> unselected_ranges, + const VArray<int> &cuts, + const Span<bool> cyclic, + MutableSpan<int> dst_curve_offsets, + MutableSpan<int> dst_point_offsets) +{ + /* Fill the array with each curve's point count, then accumulate them to the offsets. */ + bke::curves::fill_curve_counts(src_curves, unselected_ranges, dst_curve_offsets); + threading::parallel_for(selection.index_range(), 1024, [&](IndexRange range) { + for (const int curve_i : selection.slice(range)) { + const IndexRange src_points = src_curves.points_for_curve(curve_i); + const IndexRange src_segments = curve_dst_offsets(src_points, curve_i); + + MutableSpan<int> point_offsets = dst_point_offsets.slice(src_segments); + + MutableSpan<int> point_counts = point_offsets.drop_back(1); + cuts.materialize_compressed(src_points, point_counts); + for (int &count : point_counts) { + /* Make sure the number of cuts is greater than zero and add one for the existing point. */ + count = std::max(count, 0) + 1; + } + if (!cyclic[curve_i]) { + /* The last point only has a segment to be subdivided if the curve isn't cyclic. */ + point_counts.last() = 1; + } + + bke::curves::accumulate_counts_to_offsets(point_offsets); + dst_curve_offsets[curve_i] = point_offsets.last(); + } + }); + bke::curves::accumulate_counts_to_offsets(dst_curve_offsets); +} + +struct AttributeTransferData { + /* Expect that if an attribute exists, it is stored as a contiguous array internally anyway. */ + GVArraySpan src; + bke::OutputAttribute dst; +}; + +static Vector<AttributeTransferData> retrieve_point_attributes(const CurveComponent &src_component, + CurveComponent &dst_component, + const Set<std::string> &skip = {}) +{ + Vector<AttributeTransferData> attributes; + src_component.attribute_foreach( + [&](const bke::AttributeIDRef &id, const AttributeMetaData meta_data) { + if (meta_data.domain != ATTR_DOMAIN_POINT) { + /* Curve domain attributes are all copied directly to the result in one step. */ + return true; + } + if (id.is_named() && skip.contains(id.name())) { + return true; + } + + GVArray src = src_component.attribute_try_get_for_read(id, ATTR_DOMAIN_POINT); + BLI_assert(src); + bke::OutputAttribute dst = dst_component.attribute_try_get_for_output_only( + id, ATTR_DOMAIN_POINT, meta_data.data_type); + BLI_assert(dst); + attributes.append({std::move(src), std::move(dst)}); + + return true; + }); + return attributes; +} + +template<typename T> +static inline void linear_interpolation(const T &a, const T &b, MutableSpan<T> dst) +{ + dst.first() = a; + const float step = 1.0f / dst.size(); + for (const int i : dst.index_range().drop_front(1)) { + dst[i] = attribute_math::mix2(i * step, a, b); + } +} + +template<typename T> +static void subdivide_attribute_linear(const bke::CurvesGeometry &src_curves, + const bke::CurvesGeometry &dst_curves, + const IndexMask selection, + const Span<int> point_offsets, + const Span<T> src, + MutableSpan<T> dst) +{ + threading::parallel_for(selection.index_range(), 512, [&](IndexRange selection_range) { + for (const int curve_i : selection.slice(selection_range)) { + const IndexRange src_points = src_curves.points_for_curve(curve_i); + const IndexRange src_segments = curve_dst_offsets(src_points, curve_i); + const Span<int> offsets = point_offsets.slice(src_segments); + + const IndexRange dst_points = dst_curves.points_for_curve(curve_i); + const Span<T> curve_src = src.slice(src_points); + MutableSpan<T> curve_dst = dst.slice(dst_points); + + threading::parallel_for(curve_src.index_range().drop_back(1), 1024, [&](IndexRange range) { + for (const int i : range) { + const IndexRange segment_points = bke::offsets_to_range(offsets, i); + linear_interpolation(curve_src[i], curve_src[i + 1], curve_dst.slice(segment_points)); + } + }); + + const IndexRange dst_last_segment = bke::offsets_to_range(offsets, src_points.size() - 1); + linear_interpolation(curve_src.last(), curve_src.first(), dst.slice(dst_last_segment)); + } + }); +} + +static void subdivide_attribute_linear(const bke::CurvesGeometry &src_curves, + const bke::CurvesGeometry &dst_curves, + const IndexMask selection, + const Span<int> point_offsets, + const GSpan src, + GMutableSpan dst) +{ + attribute_math::convert_to_static_type(dst.type(), [&](auto dummy) { + using T = decltype(dummy); + subdivide_attribute_linear( + src_curves, dst_curves, selection, point_offsets, src.typed<T>(), dst.typed<T>()); + }); +} + +template<typename T> +static void subdivide_attribute_catmull_rom(const bke::CurvesGeometry &src_curves, + const bke::CurvesGeometry &dst_curves, + const IndexMask selection, + const Span<int> point_offsets, + const Span<bool> cyclic, + const Span<T> src, + MutableSpan<T> dst) +{ + threading::parallel_for(selection.index_range(), 512, [&](IndexRange selection_range) { + for (const int curve_i : selection.slice(selection_range)) { + const IndexRange src_points = src_curves.points_for_curve(curve_i); + const IndexRange src_segments = curve_dst_offsets(src_points, curve_i); + const IndexRange dst_points = dst_curves.points_for_curve(curve_i); + + bke::curves::catmull_rom::interpolate_to_evaluated(src.slice(src_points), + cyclic[curve_i], + point_offsets.slice(src_segments), + dst.slice(dst_points)); + } + }); +} + +static void subdivide_attribute_catmull_rom(const bke::CurvesGeometry &src_curves, + const bke::CurvesGeometry &dst_curves, + const IndexMask selection, + const Span<int> point_offsets, + const Span<bool> cyclic, + const GSpan src, + GMutableSpan dst) +{ + attribute_math::convert_to_static_type(dst.type(), [&](auto dummy) { + using T = decltype(dummy); + subdivide_attribute_catmull_rom( + src_curves, dst_curves, selection, point_offsets, cyclic, src.typed<T>(), dst.typed<T>()); + }); +} + +static void subdivide_bezier_segment(const float3 &position_prev, + const float3 &handle_prev, + const float3 &handle_next, + const float3 &position_next, + const HandleType type_prev, + const HandleType type_next, + const IndexRange segment_points, + 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 bool is_last_cyclic_segment) +{ + auto fill_segment_handle_types = [&](const HandleType type) { + /* Also change the left handle of the control point following the segment's points. And don't + * change the left handle of the first point, since that is part of the previous segment. */ + dst_types_l.slice(segment_points.shift(1)).fill(type); + dst_types_r.slice(segment_points).fill(type); + }; + + if (bke::curves::bezier::segment_is_vector(type_prev, type_next)) { + linear_interpolation(position_prev, position_next, dst_positions.slice(segment_points)); + fill_segment_handle_types(BEZIER_HANDLE_VECTOR); + } + else { + /* The first point in the segment is always copied. */ + dst_positions[segment_points.first()] = position_prev; + + /* Non-vector segments in the result curve are given free handles. This could possibly be + * improved with another pass that sets handles to aligned where possible, but currently that + * does not provide much benefit for the increased complexity. */ + fill_segment_handle_types(BEZIER_HANDLE_FREE); + + /* In order to generate a Bezier curve with the same shape as the input curve, apply the + * De Casteljau algorithm iteratively for the provided number of cuts, constantly updating the + * previous result point's right handle and the left handle at the end of the segment. */ + float3 segment_start = position_prev; + float3 segment_handle_prev = handle_prev; + float3 segment_handle_next = handle_next; + const float3 segment_end = position_next; + + for (const int i : IndexRange(segment_points.size() - 1)) { + const float parameter = 1.0f / (segment_points.size() - i); + const int point_i = segment_points[i]; + bke::curves::bezier::Insertion insert = bke::curves::bezier::insert( + segment_start, segment_handle_prev, segment_handle_next, segment_end, parameter); + + /* Copy relevant temporary data to the result. */ + dst_handles_r[point_i] = insert.handle_prev; + dst_handles_l[point_i + 1] = insert.left_handle; + dst_positions[point_i + 1] = insert.position; + + /* Update the segment to prepare it for the next subdivision. */ + segment_start = insert.position; + segment_handle_prev = insert.right_handle; + segment_handle_next = insert.handle_next; + } + + /* Copy the handles for the last segment from the working variables. */ + const int i_segment_last = is_last_cyclic_segment ? 0 : segment_points.one_after_last(); + dst_handles_r[segment_points.last()] = segment_handle_prev; + dst_handles_l[i_segment_last] = segment_handle_next; + } +} + +static void subdivide_bezier_positions(const Span<float3> src_positions, + const Span<int8_t> src_types_l, + const Span<int8_t> src_types_r, + const Span<float3> src_handles_l, + const Span<float3> src_handles_r, + const Span<int> evaluated_offsets, + const bool cyclic, + MutableSpan<float3> dst_positions, + MutableSpan<int8_t> dst_types_l, + MutableSpan<int8_t> dst_types_r, + MutableSpan<float3> dst_handles_l, + MutableSpan<float3> dst_handles_r) +{ + threading::parallel_for(src_positions.index_range().drop_back(1), 512, [&](IndexRange range) { + for (const int segment_i : range) { + const IndexRange segment = bke::offsets_to_range(evaluated_offsets, segment_i); + subdivide_bezier_segment(src_positions[segment_i], + src_handles_r[segment_i], + src_handles_l[segment_i + 1], + src_positions[segment_i + 1], + HandleType(src_types_r[segment_i]), + HandleType(src_types_l[segment_i + 1]), + segment, + dst_positions, + dst_handles_l, + dst_handles_r, + dst_types_l, + dst_types_r, + false); + } + }); + + if (cyclic) { + const int last_index = src_positions.index_range().last(); + const IndexRange segment = bke::offsets_to_range(evaluated_offsets, last_index); + const HandleType type_prev = HandleType(src_types_r.last()); + const HandleType type_next = HandleType(src_types_l.first()); + subdivide_bezier_segment(src_positions.last(), + src_handles_r.last(), + src_handles_l.first(), + src_positions.first(), + type_prev, + type_next, + segment, + dst_positions, + dst_handles_l, + dst_handles_r, + dst_types_l, + dst_types_r, + true); + + if (bke::curves::bezier::segment_is_vector(type_prev, type_next)) { + dst_types_l.first() = BEZIER_HANDLE_VECTOR; + dst_types_r.last() = BEZIER_HANDLE_VECTOR; + } + else { + dst_types_l.first() = BEZIER_HANDLE_FREE; + dst_types_r.last() = BEZIER_HANDLE_FREE; + } + } + else { + dst_positions.last() = src_positions.last(); + dst_types_l.first() = src_types_l.first(); + dst_types_r.last() = src_types_r.last(); + dst_handles_l.first() = src_handles_l.first(); + dst_handles_r.last() = src_handles_r.last(); + } + + /* TODO: It would be possible to avoid calling this for all segments besides vector segments. */ + bke::curves::bezier::calculate_auto_handles( + cyclic, dst_types_l, dst_types_r, dst_positions, dst_handles_l, dst_handles_r); +} + +Curves *subdivide_curves(const CurveComponent &src_component, + const bke::CurvesGeometry &src_curves, + const IndexMask selection, + const VArray<int> &cuts) +{ + const Vector<IndexRange> unselected_ranges = selection.extract_ranges_invert( + src_curves.curves_range()); + + /* Cyclic is accessed a lot, it's probably worth it to make sure it's a span. */ + const VArraySpan<bool> cyclic{src_curves.cyclic()}; + + Curves *dst_curves_id = create_result_curves(src_curves); + bke::CurvesGeometry &dst_curves = bke::CurvesGeometry::wrap(dst_curves_id->geometry); + CurveComponent dst_component; + dst_component.replace(dst_curves_id, GeometryOwnershipType::Editable); + + /* For each point, this contains the point offset in the corresponding result curve, + * starting at zero. For example for two curves with four points each, the values might + * look like this: + * + * | | Curve 0 | Curve 1 | + * | ------------------- |---|---|---|---|---|---|---|---|---|----| + * | Cuts | 0 | 3 | 0 | 0 | - | 2 | 0 | 0 | 4 | - | + * | New Point Count | 1 | 4 | 1 | 1 | - | 3 | 1 | 1 | 5 | - | + * | Accumulated Offsets | 0 | 1 | 5 | 6 | 7 | 0 | 3 | 4 | 5 | 10 | + * + * Storing the leading zero is unnecessary but makes the array a bit simpler to use by avoiding + * a check for the first segment, and because some existing utilities also use leading zeros. */ + Array<int> dst_point_offsets(src_curves.points_num() + src_curves.curves_num()); +#ifdef DEBUG + dst_point_offsets.fill(-1); +#endif + calculate_result_offsets(src_curves, + selection, + unselected_ranges, + cuts, + cyclic, + dst_curves.offsets_for_write(), + dst_point_offsets); + const Span<int> point_offsets = dst_point_offsets.as_span(); + + dst_curves.resize(dst_curves.offsets().last(), dst_curves.curves_num()); + + auto subdivide_catmull_rom = [&](IndexMask selection) { + for (auto &attribute : retrieve_point_attributes(src_component, dst_component)) { + subdivide_attribute_catmull_rom(src_curves, + dst_curves, + selection, + point_offsets, + cyclic, + attribute.src, + attribute.dst.as_span()); + attribute.dst.save(); + } + }; + + auto subdivide_poly = [&](IndexMask selection) { + for (auto &attribute : retrieve_point_attributes(src_component, dst_component)) { + subdivide_attribute_linear(src_curves, + dst_curves, + selection, + point_offsets, + attribute.src, + attribute.dst.as_span()); + attribute.dst.save(); + } + }; + + auto subdivide_bezier = [&](IndexMask selection) { + 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, [&](IndexRange range) { + for (const int curve_i : selection.slice(range)) { + const IndexRange src_points = src_curves.points_for_curve(curve_i); + const IndexRange src_segments = curve_dst_offsets(src_points, curve_i); + + const IndexRange dst_points = dst_curves.points_for_curve(curve_i); + subdivide_bezier_positions(src_positions.slice(src_points), + src_types_l.slice(src_points), + src_types_r.slice(src_points), + src_handles_l.slice(src_points), + src_handles_r.slice(src_points), + point_offsets.slice(src_segments), + cyclic[curve_i], + dst_positions.slice(dst_points), + dst_types_l.slice(dst_points), + dst_types_r.slice(dst_points), + dst_handles_l.slice(dst_points), + dst_handles_r.slice(dst_points)); + } + }); + + for (auto &attribute : retrieve_point_attributes(src_component, + dst_component, + {"position", + "handle_type_left", + "handle_type_right", + "handle_right", + "handle_left"})) { + subdivide_attribute_linear(src_curves, + dst_curves, + selection, + point_offsets, + attribute.src, + attribute.dst.as_span()); + attribute.dst.save(); + } + }; + + /* NURBS curves are just treated as poly curves. NURBS subdivision that maintains + * their shape may be possible, but probably wouldn't work with the "cuts" input. */ + auto subdivide_nurbs = subdivide_poly; + + bke::curves::foreach_curve_by_type(src_curves.curve_types(), + src_curves.curve_type_counts(), + selection, + subdivide_catmull_rom, + subdivide_poly, + subdivide_bezier, + subdivide_nurbs); + + if (!unselected_ranges.is_empty()) { + for (auto &attribute : retrieve_point_attributes(src_component, dst_component)) { + bke::curves::copy_point_data( + src_curves, dst_curves, unselected_ranges, attribute.src, attribute.dst.as_span()); + attribute.dst.save(); + } + } + + return dst_curves_id; +} + +} // namespace blender::geometry diff --git a/source/blender/nodes/geometry/nodes/node_geo_curve_subdivide.cc b/source/blender/nodes/geometry/nodes/node_geo_curve_subdivide.cc index 4d8745bf79e..864e6289135 100644 --- a/source/blender/nodes/geometry/nodes/node_geo_curve_subdivide.cc +++ b/source/blender/nodes/geometry/nodes/node_geo_curve_subdivide.cc @@ -1,10 +1,8 @@ /* SPDX-License-Identifier: GPL-2.0-or-later */ -#include "BLI_task.hh" -#include "BLI_timeit.hh" +#include "BKE_curves.hh" -#include "BKE_attribute_math.hh" -#include "BKE_spline.hh" +#include "GEO_subdivide_curves.hh" #include "UI_interface.h" #include "UI_resources.h" @@ -26,302 +24,6 @@ static void node_declare(NodeDeclarationBuilder &b) b.add_output<decl::Geometry>(N_("Curve")); } -static Array<int> get_subdivided_offsets(const Spline &spline, - const VArray<int> &cuts, - const int spline_offset) -{ - Array<int> offsets(spline.segments_num() + 1); - int offset = 0; - for (const int i : IndexRange(spline.segments_num())) { - offsets[i] = offset; - offset = offset + std::max(cuts[spline_offset + i], 0) + 1; - } - offsets.last() = offset; - return offsets; -} - -template<typename T> -static void subdivide_attribute(Span<T> src, - const Span<int> offsets, - const bool is_cyclic, - MutableSpan<T> dst) -{ - const int src_num = src.size(); - threading::parallel_for(IndexRange(src_num - 1), 1024, [&](IndexRange range) { - for (const int i : range) { - const int cuts = offsets[i + 1] - offsets[i]; - dst[offsets[i]] = src[i]; - const float factor_delta = cuts == 0 ? 1.0f : 1.0f / cuts; - for (const int cut : IndexRange(cuts)) { - const float factor = cut * factor_delta; - dst[offsets[i] + cut] = attribute_math::mix2(factor, src[i], src[i + 1]); - } - } - }); - - if (is_cyclic) { - const int i = src_num - 1; - const int cuts = offsets[i + 1] - offsets[i]; - dst[offsets[i]] = src.last(); - const float factor_delta = cuts == 0 ? 1.0f : 1.0f / cuts; - for (const int cut : IndexRange(cuts)) { - const float factor = cut * factor_delta; - dst[offsets[i] + cut] = attribute_math::mix2(factor, src.last(), src.first()); - } - } - else { - dst.last() = src.last(); - } -} - -/** - * In order to generate a Bezier spline with the same shape as the input spline, apply the - * De Casteljau algorithm iteratively for the provided number of cuts, constantly updating the - * previous result point's right handle and the left handle at the end of the segment. - * - * \note Non-vector segments in the result spline are given free handles. This could possibly be - * improved with another pass that sets handles to aligned where possible, but currently that does - * not provide much benefit for the increased complexity. - */ -static void subdivide_bezier_segment(const BezierSpline &src, - const int index, - const int offset, - const int result_num, - Span<float3> src_positions, - Span<float3> src_handles_left, - Span<float3> src_handles_right, - MutableSpan<float3> dst_positions, - MutableSpan<float3> dst_handles_left, - MutableSpan<float3> dst_handles_right, - MutableSpan<int8_t> dst_type_left, - MutableSpan<int8_t> dst_type_right) -{ - const bool is_last_cyclic_segment = index == (src.size() - 1); - const int next_index = is_last_cyclic_segment ? 0 : index + 1; - - /* The first point in the segment is always copied. */ - dst_positions[offset] = src_positions[index]; - - if (src.segment_is_vector(index)) { - if (is_last_cyclic_segment) { - dst_type_left.first() = BEZIER_HANDLE_VECTOR; - } - dst_type_left.slice(offset + 1, result_num).fill(BEZIER_HANDLE_VECTOR); - dst_type_right.slice(offset, result_num).fill(BEZIER_HANDLE_VECTOR); - - const float factor_delta = 1.0f / result_num; - for (const int cut : IndexRange(result_num)) { - const float factor = cut * factor_delta; - dst_positions[offset + cut] = attribute_math::mix2( - factor, src_positions[index], src_positions[next_index]); - } - } - else { - if (is_last_cyclic_segment) { - dst_type_left.first() = BEZIER_HANDLE_FREE; - } - dst_type_left.slice(offset + 1, result_num).fill(BEZIER_HANDLE_FREE); - dst_type_right.slice(offset, result_num).fill(BEZIER_HANDLE_FREE); - - const int i_segment_last = is_last_cyclic_segment ? 0 : offset + result_num; - - /* Create a Bezier segment to update iteratively for every subdivision - * and references to the meaningful values for ease of use. */ - BezierSpline temp; - temp.resize(2); - float3 &segment_start = temp.positions().first(); - float3 &segment_end = temp.positions().last(); - float3 &handle_prev = temp.handle_positions_right().first(); - float3 &handle_next = temp.handle_positions_left().last(); - segment_start = src_positions[index]; - segment_end = src_positions[next_index]; - handle_prev = src_handles_right[index]; - handle_next = src_handles_left[next_index]; - - for (const int cut : IndexRange(result_num - 1)) { - const float parameter = 1.0f / (result_num - cut); - const BezierSpline::InsertResult insert = temp.calculate_segment_insertion(0, 1, parameter); - - /* Copy relevant temporary data to the result. */ - dst_handles_right[offset + cut] = insert.handle_prev; - dst_handles_left[offset + cut + 1] = insert.left_handle; - dst_positions[offset + cut + 1] = insert.position; - - /* Update the segment to prepare it for the next subdivision. */ - segment_start = insert.position; - handle_prev = insert.right_handle; - handle_next = insert.handle_next; - } - - /* Copy the handles for the last segment from the temporary spline. */ - dst_handles_right[offset + result_num - 1] = handle_prev; - dst_handles_left[i_segment_last] = handle_next; - } -} - -static void subdivide_bezier_spline(const BezierSpline &src, - const Span<int> offsets, - BezierSpline &dst) -{ - Span<float3> src_positions = src.positions(); - Span<float3> src_handles_left = src.handle_positions_left(); - Span<float3> src_handles_right = src.handle_positions_right(); - MutableSpan<float3> dst_positions = dst.positions(); - MutableSpan<float3> dst_handles_left = dst.handle_positions_left(); - MutableSpan<float3> dst_handles_right = dst.handle_positions_right(); - MutableSpan<int8_t> dst_type_left = dst.handle_types_left(); - MutableSpan<int8_t> dst_type_right = dst.handle_types_right(); - - threading::parallel_for(IndexRange(src.size() - 1), 512, [&](IndexRange range) { - for (const int i : range) { - subdivide_bezier_segment(src, - i, - offsets[i], - offsets[i + 1] - offsets[i], - src_positions, - src_handles_left, - src_handles_right, - dst_positions, - dst_handles_left, - dst_handles_right, - dst_type_left, - dst_type_right); - } - }); - - if (src.is_cyclic()) { - const int i_last = src.size() - 1; - subdivide_bezier_segment(src, - i_last, - offsets[i_last], - offsets.last() - offsets[i_last], - src_positions, - src_handles_left, - src_handles_right, - dst_positions, - dst_handles_left, - dst_handles_right, - dst_type_left, - dst_type_right); - } - else { - dst_positions.last() = src_positions.last(); - dst_type_left.first() = src.handle_types_left().first(); - dst_type_right.last() = src.handle_types_right().last(); - dst_handles_left.first() = src_handles_left.first(); - dst_handles_right.last() = src_handles_right.last(); - } -} - -static void subdivide_builtin_attributes(const Spline &src_spline, - const Span<int> offsets, - Spline &dst_spline) -{ - const bool is_cyclic = src_spline.is_cyclic(); - subdivide_attribute<float>(src_spline.radii(), offsets, is_cyclic, dst_spline.radii()); - subdivide_attribute<float>(src_spline.tilts(), offsets, is_cyclic, dst_spline.tilts()); - switch (src_spline.type()) { - case CURVE_TYPE_POLY: { - const PolySpline &src = static_cast<const PolySpline &>(src_spline); - PolySpline &dst = static_cast<PolySpline &>(dst_spline); - subdivide_attribute<float3>(src.positions(), offsets, is_cyclic, dst.positions()); - break; - } - case CURVE_TYPE_BEZIER: { - const BezierSpline &src = static_cast<const BezierSpline &>(src_spline); - BezierSpline &dst = static_cast<BezierSpline &>(dst_spline); - subdivide_bezier_spline(src, offsets, dst); - dst.mark_cache_invalid(); - break; - } - case CURVE_TYPE_NURBS: { - const NURBSpline &src = static_cast<const NURBSpline &>(src_spline); - NURBSpline &dst = static_cast<NURBSpline &>(dst_spline); - subdivide_attribute<float3>(src.positions(), offsets, is_cyclic, dst.positions()); - subdivide_attribute<float>(src.weights(), offsets, is_cyclic, dst.weights()); - break; - } - case CURVE_TYPE_CATMULL_ROM: { - BLI_assert_unreachable(); - break; - } - } -} - -static void subdivide_dynamic_attributes(const Spline &src_spline, - const Span<int> offsets, - Spline &dst_spline) -{ - const bool is_cyclic = src_spline.is_cyclic(); - src_spline.attributes.foreach_attribute( - [&](const bke::AttributeIDRef &attribute_id, const AttributeMetaData &meta_data) { - std::optional<GSpan> src = src_spline.attributes.get_for_read(attribute_id); - BLI_assert(src); - - if (!dst_spline.attributes.create(attribute_id, meta_data.data_type)) { - /* Since the source spline of the same type had the attribute, adding it should work. */ - BLI_assert_unreachable(); - } - - std::optional<GMutableSpan> dst = dst_spline.attributes.get_for_write(attribute_id); - BLI_assert(dst); - - attribute_math::convert_to_static_type(dst->type(), [&](auto dummy) { - using T = decltype(dummy); - subdivide_attribute<T>(src->typed<T>(), offsets, is_cyclic, dst->typed<T>()); - }); - return true; - }, - ATTR_DOMAIN_POINT); -} - -static SplinePtr subdivide_spline(const Spline &spline, - const VArray<int> &cuts, - const int spline_offset) -{ - if (spline.size() <= 1) { - return spline.copy(); - } - - /* Since we expect to access each value many times, it should be worth it to make sure count - * of cuts is a real span (especially considering the note below). Using the offset at each - * point facilitates subdividing in parallel later. */ - Array<int> offsets = get_subdivided_offsets(spline, cuts, spline_offset); - const int result_num = offsets.last() + int(!spline.is_cyclic()); - SplinePtr new_spline = spline.copy_only_settings(); - new_spline->resize(result_num); - subdivide_builtin_attributes(spline, offsets, *new_spline); - subdivide_dynamic_attributes(spline, offsets, *new_spline); - return new_spline; -} - -/** - * \note Passing the virtual array for the entire spline is possibly quite inefficient here when - * the attribute was on the point domain and stored separately for each spline already, and it - * prevents some other optimizations like skipping splines with a single attribute value of < 1. - * However, it allows the node to access builtin attribute easily, so it the makes most sense this - * way until the attribute API is refactored. - */ -static std::unique_ptr<CurveEval> subdivide_curve(const CurveEval &input_curve, - const VArray<int> &cuts) -{ - const Array<int> control_point_offsets = input_curve.control_point_offsets(); - const Span<SplinePtr> input_splines = input_curve.splines(); - - std::unique_ptr<CurveEval> output_curve = std::make_unique<CurveEval>(); - output_curve->resize(input_splines.size()); - output_curve->attributes = input_curve.attributes; - MutableSpan<SplinePtr> output_splines = output_curve->splines(); - - threading::parallel_for(input_splines.index_range(), 128, [&](IndexRange range) { - for (const int i : range) { - output_splines[i] = subdivide_spline(*input_splines[i], cuts, control_point_offsets[i]); - } - }); - - return output_curve; -} - static void node_geo_exec(GeoNodeExecParams params) { GeometrySet geometry_set = params.extract_input<GeometrySet>("Curve"); @@ -333,20 +35,21 @@ static void node_geo_exec(GeoNodeExecParams params) } const CurveComponent &component = *geometry_set.get_component_for_read<CurveComponent>(); - GeometryComponentFieldContext field_context{component, ATTR_DOMAIN_POINT}; - const int domain_num = component.attribute_domain_num(ATTR_DOMAIN_POINT); + const bke::CurvesGeometry &curves = bke::CurvesGeometry::wrap( + component.get_for_read()->geometry); - fn::FieldEvaluator evaluator{field_context, domain_num}; + GeometryComponentFieldContext field_context{component, ATTR_DOMAIN_POINT}; + fn::FieldEvaluator evaluator{field_context, curves.points_num()}; evaluator.add(cuts_field); evaluator.evaluate(); - const VArray<int> &cuts = evaluator.get_evaluated<int>(0); - + const VArray<int> cuts = evaluator.get_evaluated<int>(0); if (cuts.is_single() && cuts.get_internal_single() < 1) { return; } - std::unique_ptr<CurveEval> output_curve = subdivide_curve( - *curves_to_curve_eval(*component.get_for_read()), cuts); - geometry_set.replace_curves(curve_eval_to_curves(*output_curve)); + + Curves *result = geometry::subdivide_curves(component, curves, curves.curves_range(), cuts); + + geometry_set.replace_curves(result); }); params.set_output("Curve", geometry_set); } |