/* * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License * as published by the Free Software Foundation; either version 2 * of the License, or (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software Foundation, * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #pragma once /** \file * \ingroup bke */ #include #include "FN_generic_virtual_array.hh" #include "BLI_float4x4.hh" #include "BLI_math_vec_types.hh" #include "BLI_vector.hh" #include "BKE_attribute_access.hh" #include "BKE_attribute_math.hh" struct Curve; struct ListBase; class Spline; using SplinePtr = std::unique_ptr; /** * 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: enum class Type { Bezier, NURBS, Poly, }; enum NormalCalculationMode { ZUp, Minimum, Tangent, }; NormalCalculationMode normal_mode = Minimum; blender::bke::CustomDataAttributes attributes; protected: Type type_; bool is_cyclic_ = false; /** Direction of the spline at each evaluated point. */ mutable blender::Vector 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 evaluated_normals_cache_; mutable std::mutex normal_cache_mutex_; mutable bool normal_cache_dirty_ = true; /** Accumulated lengths along the evaluated points. */ mutable blender::Vector evaluated_lengths_cache_; mutable std::mutex length_cache_mutex_; mutable bool length_cache_dirty_ = true; public: virtual ~Spline() = default; Spline(const Type 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); Spline::Type type() const; /** Return the number of control points. */ virtual int size() const = 0; int segments_size() const; bool is_cyclic() const; void set_cyclic(bool value); virtual void resize(int size) = 0; virtual blender::MutableSpan positions() = 0; virtual blender::Span positions() const = 0; virtual blender::MutableSpan radii() = 0; virtual blender::Span radii() const = 0; virtual blender::MutableSpan tilts() = 0; virtual blender::Span 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_size() const = 0; int evaluated_edges_size() const; float length() const; virtual blender::Span 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 evaluated_lengths() const; /** * Return non-owning access to the direction of the curve at each evaluated point. */ blender::Span 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 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_size - 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 sample_uniform_index_factors(int samples_size) 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::fn::GVArray &src, blender::Span index_factors, blender::fn::GMutableSpan dst) const; template void sample_with_index_factors(const blender::VArray &src, blender::Span index_factors, blender::MutableSpan dst) const { this->sample_with_index_factors( blender::fn::GVArray(src), index_factors, blender::fn::GMutableSpan(dst)); } template void sample_with_index_factors(blender::Span src, blender::Span index_factors, blender::MutableSpan dst) const { this->sample_with_index_factors(blender::VArray::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::fn::GVArray interpolate_to_evaluated(const blender::fn::GVArray &src) const = 0; blender::fn::GVArray interpolate_to_evaluated(blender::fn::GSpan data) const; template blender::VArray interpolate_to_evaluated(blender::Span data) const { return this->interpolate_to_evaluated(blender::fn::GSpan(data)).typed(); } 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 Bézier 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 { public: enum class HandleType { /** The handle can be moved anywhere, and doesn't influence the point's other handle. */ Free, /** The location is automatically calculated to be smooth. */ Auto, /** The location is calculated to point to the next/previous control point. */ Vector, /** The location is constrained to point in the opposite direction as the other handle. */ Align, }; private: blender::Vector positions_; blender::Vector radii_; blender::Vector tilts_; int resolution_; blender::Vector handle_types_left_; blender::Vector handle_types_right_; /* These are mutable to allow lazy recalculation of #Auto and #Vector handle positions. */ mutable blender::Vector handle_positions_left_; mutable blender::Vector 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 offset_cache_; mutable std::mutex offset_cache_mutex_; mutable bool offset_cache_dirty_ = true; /** Cache of evaluated positions. */ mutable blender::Vector 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 evaluated_mapping_cache_; mutable std::mutex mapping_cache_mutex_; mutable bool mapping_cache_dirty_ = true; public: BezierSpline() : Spline(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 positions() final; blender::Span positions() const final; blender::MutableSpan radii() final; blender::Span radii() const final; blender::MutableSpan tilts() final; blender::Span tilts() const final; blender::Span handle_types_left() const; blender::MutableSpan handle_types_left(); blender::Span 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 handle_positions_left(bool write_only = false); blender::Span handle_types_right() const; blender::MutableSpan handle_types_right(); blender::Span 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 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_size() 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 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 factional part. */ blender::Span evaluated_mappings() const; blender::Span 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::fn::GVArray interpolate_to_evaluated( const blender::fn::GVArray &src) const override; void evaluate_segment(int index, int next_index, blender::MutableSpan 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. * * 
   *           handle_prev         handle_next
   *                x----------------x
   *               /                  \
   *              /      x---O---x     \
   *             /        result        \
   *            /                        \
   *           O                          O
   *       point_prev                  point_next
   *
*/ 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: enum class KnotsMode { Normal, EndPoint, Bezier, }; /** Method used to recalculate the knots vector when points are added or removed. */ KnotsMode knots_mode; struct BasisCache { /** The influence at each control point `i + #start_index`. */ blender::Vector weights; /** * An offset for the start of #weights: the first control point index with a non-zero weight. */ int start_index; }; private: blender::Vector positions_; blender::Vector radii_; blender::Vector tilts_; blender::Vector 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_size(), and each value should be greater than or equal * to the previous. Only invalidated when a point is added or removed. */ mutable blender::Vector knots_; mutable std::mutex knots_mutex_; mutable bool knots_dirty_ = true; /** Cache of control point influences on each evaluated point. */ mutable blender::Vector 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 evaluated_position_cache_; mutable std::mutex position_cache_mutex_; mutable bool position_cache_dirty_ = true; public: NURBSpline() : Spline(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_size_and_order() const; int knots_size() const; void resize(int size) final; blender::MutableSpan positions() final; blender::Span positions() const final; blender::MutableSpan radii() final; blender::Span radii() const final; blender::MutableSpan tilts() final; blender::Span tilts() const final; blender::Span knots() const; blender::MutableSpan weights(); blender::Span weights() const; void mark_cache_invalid() final; int evaluated_points_size() const final; blender::Span evaluated_positions() const final; blender::fn::GVArray interpolate_to_evaluated(const blender::fn::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; blender::Span calculate_basis_cache() const; }; /** * A Poly spline is like a Bézier 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 positions_; blender::Vector radii_; blender::Vector tilts_; public: PolySpline() : Spline(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 positions() final; blender::Span positions() const final; blender::MutableSpan radii() final; blender::Span radii() const final; blender::MutableSpan tilts() final; blender::Span tilts() const final; void mark_cache_invalid() final; int evaluated_points_size() const final; blender::Span 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::fn::GVArray interpolate_to_evaluated(const blender::fn::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 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 splines() const; blender::MutableSpan 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 Spline::Type 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 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; /** * 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 control_point_offsets() const; /** * Exactly like #control_point_offsets, but uses the number of evaluated points instead. */ blender::Array 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 accumulated_spline_lengths() const; float total_length() const; int total_control_point_size() 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 curve_eval_from_dna_curve(const Curve &curve, const ListBase &nurbs_list); std::unique_ptr curve_eval_from_dna_curve(const Curve &dna_curve);