diff options
Diffstat (limited to 'source/blender/blenkernel/BKE_spline.hh')
| -rw-r--r-- | source/blender/blenkernel/BKE_spline.hh | 688 |
1 files changed, 0 insertions, 688 deletions
diff --git a/source/blender/blenkernel/BKE_spline.hh b/source/blender/blenkernel/BKE_spline.hh deleted file mode 100644 index 27542aa3586..00000000000 --- a/source/blender/blenkernel/BKE_spline.hh +++ /dev/null @@ -1,688 +0,0 @@ -/* SPDX-License-Identifier: GPL-2.0-or-later */ - -#pragma once - -/** \file - * \ingroup bke - */ - -#include <mutex> - -#include "DNA_curves_types.h" - -#include "BLI_float4x4.hh" -#include "BLI_generic_virtual_array.hh" -#include "BLI_math_vec_types.hh" -#include "BLI_vector.hh" - -#include "BKE_attribute.hh" -#include "BKE_attribute_math.hh" - -struct Curve; -struct Curves; -struct ListBase; - -class Spline; -using SplinePtr = std::unique_ptr<Spline>; - -/** - * A spline is an abstraction of a single branch-less curve section, its evaluation methods, - * and data. The spline data itself is just control points and a set of attributes by the set - * of "evaluated" data is often used instead. Conceptually, the derived vs. original data is - * an essential distinction. Derived data is usually calculated lazily and cached on the spline. - * - * Any derived class of Spline has to manage two things: - * 1. Interpolating arbitrary attribute data from the control points to evaluated points. - * 2. Evaluating the positions based on the stored control point data. - * - * Beyond that, everything is the base class's responsibility, with minor exceptions. Further - * evaluation happens in a layer on top of the evaluated points generated by the derived types. - * - * There are a few methods to evaluate a spline: - * 1. #evaluated_positions and #interpolate_to_evaluated give data for the initial - * evaluated points, depending on the resolution. - * 2. #lookup_evaluated_factor and #lookup_evaluated_factor are meant for one-off lookups - * along the length of a curve. - * 3. #sample_uniform_index_factors returns an array that stores uniform-length samples - * along the spline which can be used to interpolate data from method 1. - * - * Commonly used evaluated data is stored in caches on the spline itself so that operations on - * splines don't need to worry about taking ownership of evaluated data when they don't need to. - */ -class Spline { - public: - NormalMode normal_mode = NORMAL_MODE_MINIMUM_TWIST; - - blender::bke::CustomDataAttributes attributes; - - protected: - CurveType type_; - bool is_cyclic_ = false; - - /** Direction of the spline at each evaluated point. */ - mutable blender::Vector<blender::float3> evaluated_tangents_cache_; - mutable std::mutex tangent_cache_mutex_; - mutable bool tangent_cache_dirty_ = true; - - /** Normal direction vectors for each evaluated point. */ - mutable blender::Vector<blender::float3> evaluated_normals_cache_; - mutable std::mutex normal_cache_mutex_; - mutable bool normal_cache_dirty_ = true; - - /** Accumulated lengths along the evaluated points. */ - mutable blender::Vector<float> evaluated_lengths_cache_; - mutable std::mutex length_cache_mutex_; - mutable bool length_cache_dirty_ = true; - - public: - virtual ~Spline() = default; - Spline(const CurveType type) : type_(type) - { - } - Spline(Spline &other) : attributes(other.attributes), type_(other.type_) - { - copy_base_settings(other, *this); - } - - /** - * Return a new spline with the same data, settings, and attributes. - */ - SplinePtr copy() const; - /** - * Return a new spline with the same type and settings like "cyclic", but without any data. - */ - SplinePtr copy_only_settings() const; - /** - * The same as #copy, but skips copying dynamic attributes to the new spline. - */ - SplinePtr copy_without_attributes() const; - static void copy_base_settings(const Spline &src, Spline &dst); - - CurveType type() const; - - /** Return the number of control points. */ - virtual int size() const = 0; - int segments_num() const; - bool is_cyclic() const; - void set_cyclic(bool value); - - virtual void resize(int size) = 0; - virtual blender::MutableSpan<blender::float3> positions() = 0; - virtual blender::Span<blender::float3> positions() const = 0; - virtual blender::MutableSpan<float> radii() = 0; - virtual blender::Span<float> radii() const = 0; - virtual blender::MutableSpan<float> tilts() = 0; - virtual blender::Span<float> tilts() const = 0; - - virtual void translate(const blender::float3 &translation); - virtual void transform(const blender::float4x4 &matrix); - - /** - * Change the direction of the spline (switch the start and end) without changing its shape. - */ - void reverse(); - - /** - * Mark all caches for re-computation. This must be called after any operation that would - * change the generated positions, tangents, normals, mapping, etc. of the evaluated points. - */ - virtual void mark_cache_invalid() = 0; - virtual int evaluated_points_num() const = 0; - int evaluated_edges_num() const; - - float length() const; - - virtual blender::Span<blender::float3> evaluated_positions() const = 0; - - /** - * Return non-owning access to the cache of accumulated lengths along the spline. Each item is - * the length of the subsequent segment, i.e. the first value is the length of the first segment - * rather than 0. This calculation is rather trivial, and only depends on the evaluated - * positions. However, the results are used often, and it is necessarily single threaded, so it - * is cached. - */ - blender::Span<float> evaluated_lengths() const; - /** - * Return non-owning access to the direction of the curve at each evaluated point. - */ - blender::Span<blender::float3> evaluated_tangents() const; - /** - * Return non-owning access to the direction vectors perpendicular to the tangents at every - * evaluated point. The method used to generate the normal vectors depends on Spline.normal_mode. - */ - blender::Span<blender::float3> evaluated_normals() const; - - void bounds_min_max(blender::float3 &min, blender::float3 &max, bool use_evaluated) const; - - struct LookupResult { - /** - * The index of the evaluated point before the result location. In other words, the index of - * the edge that the result lies on. If the sampled factor/length is the very end of the - * spline, this will be the second to last index, if it's the very beginning, this will be 0. - */ - int evaluated_index; - /** - * The index of the evaluated point after the result location, accounting for wrapping when - * the spline is cyclic. If the sampled factor/length is the very end of the spline, this will - * be the last index (#evaluated_points_num - 1). - */ - int next_evaluated_index; - /** - * The portion of the way from the evaluated point at #evaluated_index to the next point. - * If the sampled factor/length is the very end of the spline, this will be the 1.0f - */ - float factor; - }; - /** - * Find the position on the evaluated spline at the given portion of the total length. - * The return value is the indices of the two neighboring points at that location and the - * factor between them, which can be used to look up any attribute on the evaluated points. - * \note This does not support extrapolation. - */ - LookupResult lookup_evaluated_factor(float factor) const; - /** - * The same as #lookup_evaluated_factor, but looks up a length directly instead of - * a portion of the total. - */ - LookupResult lookup_evaluated_length(float length) const; - - /** - * Return an array of evenly spaced samples along the length of the spline. The samples are - * indices and factors to the next index encoded in floats. The logic for converting from the - * float values to interpolation data is in #lookup_data_from_index_factor. - */ - blender::Array<float> sample_uniform_index_factors(int samples_num) const; - LookupResult lookup_data_from_index_factor(float index_factor) const; - - /** - * Sample any input data with a value for each evaluated point (already interpolated to evaluated - * points) to arbitrary parameters in between the evaluated points. The interpolation is quite - * simple, but this handles the cyclic and end point special cases. - */ - void sample_with_index_factors(const blender::GVArray &src, - blender::Span<float> index_factors, - blender::GMutableSpan dst) const; - template<typename T> - void sample_with_index_factors(const blender::VArray<T> &src, - blender::Span<float> index_factors, - blender::MutableSpan<T> dst) const - { - this->sample_with_index_factors( - blender::GVArray(src), index_factors, blender::GMutableSpan(dst)); - } - template<typename T> - void sample_with_index_factors(blender::Span<T> src, - blender::Span<float> index_factors, - blender::MutableSpan<T> dst) const - { - this->sample_with_index_factors(blender::VArray<T>::ForSpan(src), index_factors, dst); - } - - /** - * Interpolate a virtual array of data with the size of the number of control points to the - * evaluated points. For poly splines, the lifetime of the returned virtual array must not - * exceed the lifetime of the input data. - */ - virtual blender::GVArray interpolate_to_evaluated(const blender::GVArray &src) const = 0; - blender::GVArray interpolate_to_evaluated(blender::GSpan data) const; - template<typename T> blender::VArray<T> interpolate_to_evaluated(blender::Span<T> data) const - { - return this->interpolate_to_evaluated(blender::GSpan(data)).typed<T>(); - } - - protected: - virtual void correct_end_tangents() const = 0; - virtual void copy_settings(Spline &dst) const = 0; - virtual void copy_data(Spline &dst) const = 0; - virtual void reverse_impl() = 0; -}; - -/** - * A Bezier spline is made up of a many curve segments, possibly achieving continuity of curvature - * by constraining the alignment of curve handles. Evaluation stores the positions and a map of - * factors and indices in a list of floats, which is then used to interpolate any other data. - */ -class BezierSpline final : public Spline { - blender::Vector<blender::float3> positions_; - blender::Vector<float> radii_; - blender::Vector<float> tilts_; - int resolution_; - - blender::Vector<int8_t> handle_types_left_; - blender::Vector<int8_t> handle_types_right_; - - /* These are mutable to allow lazy recalculation of #Auto and #Vector handle positions. */ - mutable blender::Vector<blender::float3> handle_positions_left_; - mutable blender::Vector<blender::float3> handle_positions_right_; - - mutable std::mutex auto_handle_mutex_; - mutable bool auto_handles_dirty_ = true; - - /** Start index in evaluated points array for every control point. */ - mutable blender::Vector<int> offset_cache_; - mutable std::mutex offset_cache_mutex_; - mutable bool offset_cache_dirty_ = true; - - /** Cache of evaluated positions. */ - mutable blender::Vector<blender::float3> evaluated_position_cache_; - mutable std::mutex position_cache_mutex_; - mutable bool position_cache_dirty_ = true; - - /** Cache of "index factors" based calculated from the evaluated positions. */ - mutable blender::Vector<float> evaluated_mapping_cache_; - mutable std::mutex mapping_cache_mutex_; - mutable bool mapping_cache_dirty_ = true; - - public: - BezierSpline() : Spline(CURVE_TYPE_BEZIER) - { - } - BezierSpline(const BezierSpline &other) - : Spline((Spline &)other), - positions_(other.positions_), - radii_(other.radii_), - tilts_(other.tilts_), - resolution_(other.resolution_), - handle_types_left_(other.handle_types_left_), - handle_types_right_(other.handle_types_right_), - handle_positions_left_(other.handle_positions_left_), - handle_positions_right_(other.handle_positions_right_) - { - } - - int size() const final; - int resolution() const; - void set_resolution(int value); - - void resize(int size) final; - blender::MutableSpan<blender::float3> positions() final; - blender::Span<blender::float3> positions() const final; - blender::MutableSpan<float> radii() final; - blender::Span<float> radii() const final; - blender::MutableSpan<float> tilts() final; - blender::Span<float> tilts() const final; - blender::Span<int8_t> handle_types_left() const; - blender::MutableSpan<int8_t> handle_types_left(); - blender::Span<blender::float3> handle_positions_left() const; - /** - * Get writable access to the handle position. - * - * \param write_only: pass true for an uninitialized spline, this prevents accessing - * uninitialized memory while auto-generating handles. - */ - blender::MutableSpan<blender::float3> handle_positions_left(bool write_only = false); - blender::Span<int8_t> handle_types_right() const; - blender::MutableSpan<int8_t> handle_types_right(); - blender::Span<blender::float3> handle_positions_right() const; - /** - * Get writable access to the handle position. - * - * \param write_only: pass true for an uninitialized spline, this prevents accessing - * uninitialized memory while auto-generating handles. - */ - blender::MutableSpan<blender::float3> handle_positions_right(bool write_only = false); - /** - * Recalculate all #Auto and #Vector handles with positions automatically - * derived from the neighboring control points. - */ - void ensure_auto_handles() const; - - void translate(const blender::float3 &translation) override; - void transform(const blender::float4x4 &matrix) override; - - /** - * Set positions for the right handle of the control point, ensuring that - * aligned handles stay aligned. Has no effect for auto and vector type handles. - */ - void set_handle_position_right(int index, const blender::float3 &value); - /** - * Set positions for the left handle of the control point, ensuring that - * aligned handles stay aligned. Has no effect for auto and vector type handles. - */ - void set_handle_position_left(int index, const blender::float3 &value); - - bool point_is_sharp(int index) const; - - void mark_cache_invalid() final; - int evaluated_points_num() const final; - - /** - * Returns access to a cache of offsets into the evaluated point array for each control point. - * While most control point edges generate the number of edges specified by the resolution, - * vector segments only generate one edge. - * - * \note The length of the result is one greater than the number of points, so that the last item - * is the total number of evaluated points. This is useful to avoid recalculating the size of the - * last segment everywhere. - */ - blender::Span<int> control_point_offsets() const; - /** - * Returns non-owning access to an array of values containing the information necessary to - * interpolate values from the original control points to evaluated points. The control point - * index is the integer part of each value, and the factor used for interpolating to the next - * control point is the remaining fractional part. - */ - blender::Span<float> evaluated_mappings() const; - blender::Span<blender::float3> evaluated_positions() const final; - struct InterpolationData { - int control_point_index; - int next_control_point_index; - /** - * Linear interpolation weight between the two indices, from 0 to 1. - * Higher means closer to next control point. - */ - float factor; - }; - /** - * Convert the data encoded in #evaulated_mappings into its parts-- the information necessary - * to interpolate data from control points to evaluated points between them. The next control - * point index result will not overflow the size of the control point vectors. - */ - InterpolationData interpolation_data_from_index_factor(float index_factor) const; - - virtual blender::GVArray interpolate_to_evaluated(const blender::GVArray &src) const override; - - void evaluate_segment(int index, - int next_index, - blender::MutableSpan<blender::float3> positions) const; - /** - * \warning This functional assumes that the spline has more than one point. - */ - bool segment_is_vector(int start_index) const; - - /** See comment and diagram for #calculate_segment_insertion. */ - struct InsertResult { - blender::float3 handle_prev; - blender::float3 left_handle; - blender::float3 position; - blender::float3 right_handle; - blender::float3 handle_next; - }; - /** - * De Casteljau Bezier subdivision. - * \param index: The index of the segment's start control point. - * \param next_index: The index of the control point at the end of the segment. Could be 0, - * if the spline is cyclic. - * \param parameter: The factor along the segment, between 0 and 1. Note that this is used - * directly by the calculation, it doesn't correspond to a portion of the evaluated length. - * - * <pre> - * handle_prev handle_next - * x----------------x - * / \ - * / x---O---x \ - * / result \ - * / \ - * O O - * point_prev point_next - * </pre> - */ - InsertResult calculate_segment_insertion(int index, int next_index, float parameter); - - private: - /** - * If the spline is not cyclic, the direction for the first and last points is just the - * direction formed by the corresponding handles and control points. In the unlikely situation - * that the handles define a zero direction, fallback to using the direction defined by the - * first and last evaluated segments already calculated in #Spline::evaluated_tangents(). - */ - void correct_end_tangents() const final; - void copy_settings(Spline &dst) const final; - void copy_data(Spline &dst) const final; - - protected: - void reverse_impl() override; -}; - -/** - * Data for Non-Uniform Rational B-Splines. The mapping from control points to evaluated points is - * influenced by a vector of knots, weights for each point, and the order of the spline. Every - * mapping of data to evaluated points is handled the same way, but the positions are cached in - * the spline. - */ -class NURBSpline final : public Spline { - public: - /** Method used to recalculate the knots vector when points are added or removed. */ - KnotsMode knots_mode; - - struct BasisCache { - /** - * For each evaluated point, the weight for all control points that influences it. - * The vector's size is the evaluated point count multiplied by the spline's order. - */ - blender::Vector<float> weights; - /** - * An offset for the start of #weights: the first control point index with a non-zero weight. - */ - blender::Vector<int> start_indices; - }; - - private: - blender::Vector<blender::float3> positions_; - blender::Vector<float> radii_; - blender::Vector<float> tilts_; - blender::Vector<float> weights_; - int resolution_; - /** - * Defines the number of nearby control points that influence a given evaluated point. Higher - * orders give smoother results. The number of control points must be greater than or equal to - * this value. - */ - uint8_t order_; - - /** - * Determines where and how the control points affect the evaluated points. The length should - * always be the value returned by #knots_num(), and each value should be greater than or equal - * to the previous. Only invalidated when a point is added or removed. - */ - mutable blender::Vector<float> knots_; - mutable std::mutex knots_mutex_; - mutable bool knots_dirty_ = true; - - /** Cache of control point influences on each evaluated point. */ - mutable BasisCache basis_cache_; - mutable std::mutex basis_cache_mutex_; - mutable bool basis_cache_dirty_ = true; - - /** - * Cache of position data calculated from the basis cache. Though it is interpolated - * in the same way as any other attribute, it is stored to save unnecessary recalculation. - */ - mutable blender::Vector<blender::float3> evaluated_position_cache_; - mutable std::mutex position_cache_mutex_; - mutable bool position_cache_dirty_ = true; - - public: - NURBSpline() : Spline(CURVE_TYPE_NURBS) - { - } - NURBSpline(const NURBSpline &other) - : Spline((Spline &)other), - knots_mode(other.knots_mode), - positions_(other.positions_), - radii_(other.radii_), - tilts_(other.tilts_), - weights_(other.weights_), - resolution_(other.resolution_), - order_(other.order_) - { - } - - int size() const final; - int resolution() const; - void set_resolution(int value); - uint8_t order() const; - void set_order(uint8_t value); - - bool check_valid_num_and_order() const; - int knots_num() const; - - void resize(int size) final; - blender::MutableSpan<blender::float3> positions() final; - blender::Span<blender::float3> positions() const final; - blender::MutableSpan<float> radii() final; - blender::Span<float> radii() const final; - blender::MutableSpan<float> tilts() final; - blender::Span<float> tilts() const final; - blender::Span<float> knots() const; - - blender::MutableSpan<float> weights(); - blender::Span<float> weights() const; - - void mark_cache_invalid() final; - int evaluated_points_num() const final; - - blender::Span<blender::float3> evaluated_positions() const final; - - blender::GVArray interpolate_to_evaluated(const blender::GVArray &src) const final; - - protected: - void correct_end_tangents() const final; - void copy_settings(Spline &dst) const final; - void copy_data(Spline &dst) const final; - void reverse_impl() override; - - void calculate_knots() const; - const BasisCache &calculate_basis_cache() const; -}; - -/** - * A Poly spline is like a Bezier spline with a resolution of one. The main reason to distinguish - * the two is for reduced complexity and increased performance, since interpolating data to control - * points does not change it. - * - * Poly spline code is very simple, since it doesn't do anything that the base #Spline doesn't - * handle. Mostly it just worries about storing the data used by the base class. - */ -class PolySpline final : public Spline { - blender::Vector<blender::float3> positions_; - blender::Vector<float> radii_; - blender::Vector<float> tilts_; - - public: - PolySpline() : Spline(CURVE_TYPE_POLY) - { - } - PolySpline(const PolySpline &other) - : Spline((Spline &)other), - positions_(other.positions_), - radii_(other.radii_), - tilts_(other.tilts_) - { - } - - int size() const final; - - void resize(int size) final; - blender::MutableSpan<blender::float3> positions() final; - blender::Span<blender::float3> positions() const final; - blender::MutableSpan<float> radii() final; - blender::Span<float> radii() const final; - blender::MutableSpan<float> tilts() final; - blender::Span<float> tilts() const final; - - void mark_cache_invalid() final; - int evaluated_points_num() const final; - - blender::Span<blender::float3> evaluated_positions() const final; - - /** - * Poly spline interpolation from control points to evaluated points is a special case, since - * the result data is the same as the input data. This function returns a #GVArray that points to - * the original data. Therefore the lifetime of the returned virtual array must not be longer - * than the source data. - */ - blender::GVArray interpolate_to_evaluated(const blender::GVArray &src) const final; - - protected: - void correct_end_tangents() const final; - void copy_settings(Spline &dst) const final; - void copy_data(Spline &dst) const final; - void reverse_impl() override; -}; - -/** - * A collection of #Spline objects with the same attribute types and names. Most data and - * functionality is in splines, but this contains some helpers for working with them as a group. - * - * \note A #CurveEval corresponds to the #Curve object data. The name is different for clarity, - * since more of the data is stored in the splines, but also just to be different than the name in - * DNA. - */ -struct CurveEval { - private: - blender::Vector<SplinePtr> splines_; - - public: - blender::bke::CustomDataAttributes attributes; - - CurveEval() = default; - CurveEval(const CurveEval &other) : attributes(other.attributes) - { - for (const SplinePtr &spline : other.splines()) { - this->add_spline(spline->copy()); - } - } - - blender::Span<SplinePtr> splines() const; - blender::MutableSpan<SplinePtr> splines(); - /** - * \return True if the curve contains a spline with the given type. - * - * \note If you are looping over all of the splines in the same scope anyway, - * it's better to avoid calling this function, in case there are many splines. - */ - bool has_spline_with_type(const CurveType type) const; - - void resize(int size); - /** - * \warning Call #reallocate on the spline's attributes after adding all splines. - */ - void add_spline(SplinePtr spline); - void add_splines(blender::MutableSpan<SplinePtr> splines); - void remove_splines(blender::IndexMask mask); - - void translate(const blender::float3 &translation); - void transform(const blender::float4x4 &matrix); - bool bounds_min_max(blender::float3 &min, blender::float3 &max, bool use_evaluated) const; - - blender::bke::MutableAttributeAccessor attributes_for_write(); - - /** - * Return the start indices for each of the curve spline's control points, if they were part - * of a flattened array. This can be used to facilitate parallelism by avoiding the need to - * accumulate an offset while doing more complex calculations. - * - * \note The result is one longer than the spline count; the last element is the total size. - */ - blender::Array<int> control_point_offsets() const; - /** - * Exactly like #control_point_offsets, but uses the number of evaluated points instead. - */ - blender::Array<int> evaluated_point_offsets() const; - /** - * Return the accumulated length at the start of every spline in the curve. - * \note The result is one longer than the spline count; the last element is the total length. - */ - blender::Array<float> accumulated_spline_lengths() const; - - float total_length() const; - int total_control_point_num() const; - - void mark_cache_invalid(); - - /** - * Check the invariants that curve control point attributes should always uphold, necessary - * because attributes are stored on splines rather than in a flat array on the curve: - * - The same set of attributes exists on every spline. - * - Attributes with the same name have the same type on every spline. - * - Attributes are in the same order on every spline. - */ - void assert_valid_point_attributes() const; -}; - -std::unique_ptr<CurveEval> curve_eval_from_dna_curve(const Curve &curve, - const ListBase &nurbs_list); -std::unique_ptr<CurveEval> curve_eval_from_dna_curve(const Curve &dna_curve); -std::unique_ptr<CurveEval> curves_to_curve_eval(const Curves &curves); -Curves *curve_eval_to_curves(const CurveEval &curve_eval); |