From c21199a0ba7fd0cf32b2f3371b8967c4191e5d5a Mon Sep 17 00:00:00 2001 From: Hans Goudey Date: Thu, 22 Apr 2021 09:37:53 -0500 Subject: Geometry Nodes Curves: Rename files --- source/blender/blenkernel/BKE_derived_curve.hh | 436 -------------------- source/blender/blenkernel/BKE_spline.hh | 436 ++++++++++++++++++++ source/blender/blenkernel/CMakeLists.txt | 10 +- source/blender/blenkernel/intern/derived_curve.cc | 2 +- .../blenkernel/intern/derived_curve_spline_base.cc | 359 ---------------- .../intern/derived_curve_spline_bezier.cc | 378 ----------------- .../intern/derived_curve_spline_nurbs.cc | 451 --------------------- .../blenkernel/intern/derived_curve_spline_poly.cc | 143 ------- source/blender/blenkernel/intern/displist.cc | 2 +- .../blenkernel/intern/geometry_component_curve.cc | 8 +- source/blender/blenkernel/intern/geometry_set.cc | 2 +- source/blender/blenkernel/intern/spline_base.cc | 359 ++++++++++++++++ source/blender/blenkernel/intern/spline_bezier.cc | 378 +++++++++++++++++ source/blender/blenkernel/intern/spline_nurbs.cc | 451 +++++++++++++++++++++ source/blender/blenkernel/intern/spline_poly.cc | 143 +++++++ .../geometry/nodes/node_geo_curve_sample_points.cc | 2 +- .../nodes/geometry/nodes/node_geo_curve_to_mesh.cc | 2 +- .../nodes/geometry/nodes/node_geo_curve_trim.cc | 2 +- .../nodes/geometry/nodes/node_geo_join_geometry.cc | 2 +- .../nodes/geometry/nodes/node_geo_object_info.cc | 2 +- .../nodes/geometry/nodes/node_geo_transform.cc | 2 +- 21 files changed, 1786 insertions(+), 1784 deletions(-) delete mode 100644 source/blender/blenkernel/BKE_derived_curve.hh create mode 100644 source/blender/blenkernel/BKE_spline.hh delete mode 100644 source/blender/blenkernel/intern/derived_curve_spline_base.cc delete mode 100644 source/blender/blenkernel/intern/derived_curve_spline_bezier.cc delete mode 100644 source/blender/blenkernel/intern/derived_curve_spline_nurbs.cc delete mode 100644 source/blender/blenkernel/intern/derived_curve_spline_poly.cc create mode 100644 source/blender/blenkernel/intern/spline_base.cc create mode 100644 source/blender/blenkernel/intern/spline_bezier.cc create mode 100644 source/blender/blenkernel/intern/spline_nurbs.cc create mode 100644 source/blender/blenkernel/intern/spline_poly.cc (limited to 'source/blender') diff --git a/source/blender/blenkernel/BKE_derived_curve.hh b/source/blender/blenkernel/BKE_derived_curve.hh deleted file mode 100644 index 5834437b7a1..00000000000 --- a/source/blender/blenkernel/BKE_derived_curve.hh +++ /dev/null @@ -1,436 +0,0 @@ -/* - * 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_float3.hh" -#include "BLI_float4x4.hh" -#include "BLI_vector.hh" - -#include "BKE_attribute_math.hh" - -struct Curve; - -/** - * Contains the information necessary to interpolate values from the original control points to - * evaluated points. - */ -struct PointMapping { - /** - * The index of the control point preceding the evaluated point at this index. - * For resolutions higher than 1, many evaluated points can share the same value. - */ - int control_point_index; - /** - * This evaluated point's portion of the total length between the `control_point_index` value - * and the next. - */ - float factor; -}; - -/** - * A spline is an abstraction of a curve section, its evaluation methods, and data. - * The spline data itself is just control points and a set of attributes. - * - * Common evaluated data is stored in caches on the spline itself. This way operations on splines - * don't need to worry about taking ownership of evaluated data when they don't need to. - */ -class Spline { - public: - using SplinePtr = std::unique_ptr; - - enum Type { - Bezier, - NURBS, - Poly, - }; - Type type; - bool is_cyclic = false; - - enum NormalCalculationMode { - ZUp, - Minimum, - Tangent, - }; - NormalCalculationMode normal_mode; - - protected: - mutable bool base_cache_dirty_ = true; - mutable std::mutex base_cache_mutex_; - mutable blender::Vector evaluated_positions_cache_; - mutable blender::Vector evaluated_mapping_cache_; - - mutable bool tangent_cache_dirty_ = true; - mutable std::mutex tangent_cache_mutex_; - mutable blender::Vector evaluated_tangents_cache_; - - mutable bool normal_cache_dirty_ = true; - mutable std::mutex normal_cache_mutex_; - mutable blender::Vector evaluated_normals_cache_; - - mutable bool length_cache_dirty_ = true; - mutable std::mutex length_cache_mutex_; - mutable blender::Vector evaluated_lengths_cache_; - - public: - virtual ~Spline() = default; - Spline() = default; - Spline(Spline &other) - : type(other.type), is_cyclic(other.is_cyclic), normal_mode(other.normal_mode) - { - if (!other.base_cache_dirty_) { - evaluated_positions_cache_ = other.evaluated_positions_cache_; - evaluated_mapping_cache_ = other.evaluated_mapping_cache_; - base_cache_dirty_ = false; - } - if (!other.tangent_cache_dirty_) { - evaluated_tangents_cache_ = other.evaluated_tangents_cache_; - tangent_cache_dirty_ = false; - } - if (!other.normal_cache_dirty_) { - evaluated_normals_cache_ = other.evaluated_normals_cache_; - normal_cache_dirty_ = false; - } - if (!other.length_cache_dirty_) { - evaluated_lengths_cache_ = other.evaluated_lengths_cache_; - length_cache_dirty_ = false; - } - } - - virtual SplinePtr copy() const = 0; - - virtual int size() const = 0; - int segments_size() const; - virtual int resolution() const = 0; - virtual void set_resolution(const int value) = 0; - - virtual void drop_front(const int count) = 0; - virtual void drop_back(const int count) = 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 mark_cache_invalid(); - virtual int evaluated_points_size() const = 0; - int evaluated_edges_size() const; - - float length() const; - - blender::Span evaluated_positions() const; - blender::Span evaluated_mappings() const; - blender::Span evaluated_lengths() const; - blender::Span evaluated_tangents() const; - blender::Span evaluated_normals() 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. - */ - int evaluated_index; - /** - * The portion of the way from the evaluated point at #index to the next point. - */ - float factor; - }; - LookupResult lookup_evaluated_factor(const float factor) const; - LookupResult lookup_evaluated_length(const float length) const; - - /** - * Interpolate data from the original control points to the corresponding ealuated points. - * \param source_data: Should have the same size as the number of control points. - * \param result_data: ... - */ - template - void interpolate_data_to_evaluated_points(blender::Span source_data, - blender::MutableSpan result_data, - const int offset = 0) const - { - /* TODO: Onstead of "offset", it may be better to split a function that returns a single value. - * TODO: Check for null default mixer, possibly using std::enable_if? */ - const int control_points_len = this->size(); - blender::Span mappings = this->evaluated_mappings(); - - blender::attribute_math::DefaultMixer mixer(result_data); - - for (const int i : result_data.index_range()) { - const int evaluated_point_index = offset + i; - const PointMapping &mapping = mappings[evaluated_point_index]; - const int index = mapping.control_point_index; - const int next_index = (index + 1) % control_points_len; - const float factor = mapping.factor; - - const T &value = source_data[index]; - const T &next_value = source_data[next_index]; - - mixer.mix_in(i, value, 1.0f - factor); - mixer.mix_in(i, next_value, factor); - } - - mixer.finalize(); - } - - protected: - virtual void correct_end_tangents() const = 0; - virtual void ensure_base_cache() const = 0; -}; - -using SplinePtr = std::unique_ptr; - -class BezierSpline final : public Spline { - public: - enum HandleType { - Free, - Auto, - Vector, - Align, - }; - - private: - blender::Vector handle_types_start_; - blender::Vector handle_positions_start_; - blender::Vector positions_; - blender::Vector handle_types_end_; - blender::Vector handle_positions_end_; - blender::Vector radii_; - blender::Vector tilts_; - int resolution_u_; - - public: - virtual SplinePtr copy() const final; - BezierSpline() = default; - BezierSpline(const BezierSpline &other) - : Spline((Spline &)other), - handle_types_start_(other.handle_types_start_), - handle_positions_start_(other.handle_positions_start_), - positions_(other.positions_), - handle_types_end_(other.handle_types_end_), - handle_positions_end_(other.handle_positions_end_), - radii_(other.radii_), - tilts_(other.tilts_), - resolution_u_(other.resolution_u_) - { - } - - int size() const final; - int resolution() const final; - void set_resolution(const int value) 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_start() const; - blender::MutableSpan handle_types_start(); - blender::Span handle_positions_start() const; - blender::MutableSpan handle_positions_start(); - blender::Span handle_types_end() const; - blender::MutableSpan handle_types_end(); - blender::Span handle_positions_end() const; - blender::MutableSpan handle_positions_end(); - - void add_point(const blender::float3 position, - const HandleType handle_type_start, - const blender::float3 handle_position_start, - const HandleType handle_type_end, - const blender::float3 handle_position_end, - const float radius, - const float tilt); - - void drop_front(const int count) final; - void drop_back(const int count) final; - - int evaluated_points_size() const final; - - bool point_is_sharp(const int index) const; - bool handle_start_is_automatic(const int index) const; - bool handle_end_is_automatic(const int index) const; - - void move_control_point(const int index, const blender::float3 new_position); - - protected: - void correct_final_tangents() const; - - private: - void correct_end_tangents() const final; - void ensure_base_cache() const final; - bool segment_is_vector(const int start_index) const; - void evaluate_bezier_segment(const int index, - const int next_index, - int &offset, - blender::MutableSpan positions, - blender::MutableSpan mappings) const; - void evaluate_bezier_position_and_mapping(blender::MutableSpan positions, - blender::MutableSpan mappings) const; -}; - -class NURBSpline final : public Spline { - public: - enum KnotsMode { - Normal, - EndPoint, - Bezier, - }; - KnotsMode knots_mode; - - struct WeightCache { - blender::Vector weights; - int start_index; - }; - - private: - blender::Vector positions_; - blender::Vector radii_; - blender::Vector tilts_; - blender::Vector weights_; - int resolution_u_; - uint8_t order_; - - mutable bool knots_dirty_ = true; - mutable std::mutex knots_mutex_; - mutable blender::Vector knots_; - - mutable bool weights_dirty_ = true; - mutable std::mutex weights_mutex_; - mutable blender::Vector weight_cache_; - - public: - SplinePtr copy() const final; - NURBSpline() = default; - NURBSpline(const NURBSpline &other) - : Spline((Spline &)other), - positions_(other.positions_), - radii_(other.radii_), - tilts_(other.tilts_), - weights_(other.weights_), - resolution_u_(other.resolution_u_), - order_(other.order_) - { - } - - int size() const final; - int resolution() const final; - void set_resolution(const int value) final; - uint8_t order() const; - void set_order(const uint8_t value); - - bool check_valid_size_and_order() const; - int knots_size() const; - - 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 add_point(const blender::float3 position, - const float radius, - const float tilt, - const float weight); - - void drop_front(const int count) final; - void drop_back(const int count) final; - - int evaluated_points_size() const final; - - blender::fn::GVArrayPtr interpolate_to_evaluated_points( - const blender::fn::GVArray &source_data) const; - - protected: - void correct_end_tangents() const final; - void ensure_base_cache() const final; - void calculate_knots() const; - void calculate_weights() const; -}; - -class PolySpline final : public Spline { - public: - blender::Vector positions_; - blender::Vector radii_; - blender::Vector tilts_; - - private: - public: - SplinePtr copy() const final; - PolySpline() = default; - PolySpline(const PolySpline &other) - : Spline((Spline &)other), - positions_(other.positions_), - radii_(other.radii_), - tilts_(other.tilts_) - { - } - - int size() const final; - int resolution() const final; - void set_resolution(const int value) 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 add_point(const blender::float3 position, const float radius, const float tilt); - - void drop_front(const int count) final; - void drop_back(const int count) final; - - int evaluated_points_size() const final; - - protected: - void correct_end_tangents() const final; - void ensure_base_cache() const final; -}; - -/* Proposed name to be different from DNA type. */ -class DCurve { - public: - blender::Vector splines; - - // bool is_2d; - - DCurve *copy(); - - // DCurve *copy(); - - void translate(const blender::float3 translation); - void transform(const blender::float4x4 &matrix); -}; - -DCurve *dcurve_from_dna_curve(const Curve &curve); \ No newline at end of file diff --git a/source/blender/blenkernel/BKE_spline.hh b/source/blender/blenkernel/BKE_spline.hh new file mode 100644 index 00000000000..5834437b7a1 --- /dev/null +++ b/source/blender/blenkernel/BKE_spline.hh @@ -0,0 +1,436 @@ +/* + * 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_float3.hh" +#include "BLI_float4x4.hh" +#include "BLI_vector.hh" + +#include "BKE_attribute_math.hh" + +struct Curve; + +/** + * Contains the information necessary to interpolate values from the original control points to + * evaluated points. + */ +struct PointMapping { + /** + * The index of the control point preceding the evaluated point at this index. + * For resolutions higher than 1, many evaluated points can share the same value. + */ + int control_point_index; + /** + * This evaluated point's portion of the total length between the `control_point_index` value + * and the next. + */ + float factor; +}; + +/** + * A spline is an abstraction of a curve section, its evaluation methods, and data. + * The spline data itself is just control points and a set of attributes. + * + * Common evaluated data is stored in caches on the spline itself. This way operations on splines + * don't need to worry about taking ownership of evaluated data when they don't need to. + */ +class Spline { + public: + using SplinePtr = std::unique_ptr; + + enum Type { + Bezier, + NURBS, + Poly, + }; + Type type; + bool is_cyclic = false; + + enum NormalCalculationMode { + ZUp, + Minimum, + Tangent, + }; + NormalCalculationMode normal_mode; + + protected: + mutable bool base_cache_dirty_ = true; + mutable std::mutex base_cache_mutex_; + mutable blender::Vector evaluated_positions_cache_; + mutable blender::Vector evaluated_mapping_cache_; + + mutable bool tangent_cache_dirty_ = true; + mutable std::mutex tangent_cache_mutex_; + mutable blender::Vector evaluated_tangents_cache_; + + mutable bool normal_cache_dirty_ = true; + mutable std::mutex normal_cache_mutex_; + mutable blender::Vector evaluated_normals_cache_; + + mutable bool length_cache_dirty_ = true; + mutable std::mutex length_cache_mutex_; + mutable blender::Vector evaluated_lengths_cache_; + + public: + virtual ~Spline() = default; + Spline() = default; + Spline(Spline &other) + : type(other.type), is_cyclic(other.is_cyclic), normal_mode(other.normal_mode) + { + if (!other.base_cache_dirty_) { + evaluated_positions_cache_ = other.evaluated_positions_cache_; + evaluated_mapping_cache_ = other.evaluated_mapping_cache_; + base_cache_dirty_ = false; + } + if (!other.tangent_cache_dirty_) { + evaluated_tangents_cache_ = other.evaluated_tangents_cache_; + tangent_cache_dirty_ = false; + } + if (!other.normal_cache_dirty_) { + evaluated_normals_cache_ = other.evaluated_normals_cache_; + normal_cache_dirty_ = false; + } + if (!other.length_cache_dirty_) { + evaluated_lengths_cache_ = other.evaluated_lengths_cache_; + length_cache_dirty_ = false; + } + } + + virtual SplinePtr copy() const = 0; + + virtual int size() const = 0; + int segments_size() const; + virtual int resolution() const = 0; + virtual void set_resolution(const int value) = 0; + + virtual void drop_front(const int count) = 0; + virtual void drop_back(const int count) = 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 mark_cache_invalid(); + virtual int evaluated_points_size() const = 0; + int evaluated_edges_size() const; + + float length() const; + + blender::Span evaluated_positions() const; + blender::Span evaluated_mappings() const; + blender::Span evaluated_lengths() const; + blender::Span evaluated_tangents() const; + blender::Span evaluated_normals() 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. + */ + int evaluated_index; + /** + * The portion of the way from the evaluated point at #index to the next point. + */ + float factor; + }; + LookupResult lookup_evaluated_factor(const float factor) const; + LookupResult lookup_evaluated_length(const float length) const; + + /** + * Interpolate data from the original control points to the corresponding ealuated points. + * \param source_data: Should have the same size as the number of control points. + * \param result_data: ... + */ + template + void interpolate_data_to_evaluated_points(blender::Span source_data, + blender::MutableSpan result_data, + const int offset = 0) const + { + /* TODO: Onstead of "offset", it may be better to split a function that returns a single value. + * TODO: Check for null default mixer, possibly using std::enable_if? */ + const int control_points_len = this->size(); + blender::Span mappings = this->evaluated_mappings(); + + blender::attribute_math::DefaultMixer mixer(result_data); + + for (const int i : result_data.index_range()) { + const int evaluated_point_index = offset + i; + const PointMapping &mapping = mappings[evaluated_point_index]; + const int index = mapping.control_point_index; + const int next_index = (index + 1) % control_points_len; + const float factor = mapping.factor; + + const T &value = source_data[index]; + const T &next_value = source_data[next_index]; + + mixer.mix_in(i, value, 1.0f - factor); + mixer.mix_in(i, next_value, factor); + } + + mixer.finalize(); + } + + protected: + virtual void correct_end_tangents() const = 0; + virtual void ensure_base_cache() const = 0; +}; + +using SplinePtr = std::unique_ptr; + +class BezierSpline final : public Spline { + public: + enum HandleType { + Free, + Auto, + Vector, + Align, + }; + + private: + blender::Vector handle_types_start_; + blender::Vector handle_positions_start_; + blender::Vector positions_; + blender::Vector handle_types_end_; + blender::Vector handle_positions_end_; + blender::Vector radii_; + blender::Vector tilts_; + int resolution_u_; + + public: + virtual SplinePtr copy() const final; + BezierSpline() = default; + BezierSpline(const BezierSpline &other) + : Spline((Spline &)other), + handle_types_start_(other.handle_types_start_), + handle_positions_start_(other.handle_positions_start_), + positions_(other.positions_), + handle_types_end_(other.handle_types_end_), + handle_positions_end_(other.handle_positions_end_), + radii_(other.radii_), + tilts_(other.tilts_), + resolution_u_(other.resolution_u_) + { + } + + int size() const final; + int resolution() const final; + void set_resolution(const int value) 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_start() const; + blender::MutableSpan handle_types_start(); + blender::Span handle_positions_start() const; + blender::MutableSpan handle_positions_start(); + blender::Span handle_types_end() const; + blender::MutableSpan handle_types_end(); + blender::Span handle_positions_end() const; + blender::MutableSpan handle_positions_end(); + + void add_point(const blender::float3 position, + const HandleType handle_type_start, + const blender::float3 handle_position_start, + const HandleType handle_type_end, + const blender::float3 handle_position_end, + const float radius, + const float tilt); + + void drop_front(const int count) final; + void drop_back(const int count) final; + + int evaluated_points_size() const final; + + bool point_is_sharp(const int index) const; + bool handle_start_is_automatic(const int index) const; + bool handle_end_is_automatic(const int index) const; + + void move_control_point(const int index, const blender::float3 new_position); + + protected: + void correct_final_tangents() const; + + private: + void correct_end_tangents() const final; + void ensure_base_cache() const final; + bool segment_is_vector(const int start_index) const; + void evaluate_bezier_segment(const int index, + const int next_index, + int &offset, + blender::MutableSpan positions, + blender::MutableSpan mappings) const; + void evaluate_bezier_position_and_mapping(blender::MutableSpan positions, + blender::MutableSpan mappings) const; +}; + +class NURBSpline final : public Spline { + public: + enum KnotsMode { + Normal, + EndPoint, + Bezier, + }; + KnotsMode knots_mode; + + struct WeightCache { + blender::Vector weights; + int start_index; + }; + + private: + blender::Vector positions_; + blender::Vector radii_; + blender::Vector tilts_; + blender::Vector weights_; + int resolution_u_; + uint8_t order_; + + mutable bool knots_dirty_ = true; + mutable std::mutex knots_mutex_; + mutable blender::Vector knots_; + + mutable bool weights_dirty_ = true; + mutable std::mutex weights_mutex_; + mutable blender::Vector weight_cache_; + + public: + SplinePtr copy() const final; + NURBSpline() = default; + NURBSpline(const NURBSpline &other) + : Spline((Spline &)other), + positions_(other.positions_), + radii_(other.radii_), + tilts_(other.tilts_), + weights_(other.weights_), + resolution_u_(other.resolution_u_), + order_(other.order_) + { + } + + int size() const final; + int resolution() const final; + void set_resolution(const int value) final; + uint8_t order() const; + void set_order(const uint8_t value); + + bool check_valid_size_and_order() const; + int knots_size() const; + + 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 add_point(const blender::float3 position, + const float radius, + const float tilt, + const float weight); + + void drop_front(const int count) final; + void drop_back(const int count) final; + + int evaluated_points_size() const final; + + blender::fn::GVArrayPtr interpolate_to_evaluated_points( + const blender::fn::GVArray &source_data) const; + + protected: + void correct_end_tangents() const final; + void ensure_base_cache() const final; + void calculate_knots() const; + void calculate_weights() const; +}; + +class PolySpline final : public Spline { + public: + blender::Vector positions_; + blender::Vector radii_; + blender::Vector tilts_; + + private: + public: + SplinePtr copy() const final; + PolySpline() = default; + PolySpline(const PolySpline &other) + : Spline((Spline &)other), + positions_(other.positions_), + radii_(other.radii_), + tilts_(other.tilts_) + { + } + + int size() const final; + int resolution() const final; + void set_resolution(const int value) 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 add_point(const blender::float3 position, const float radius, const float tilt); + + void drop_front(const int count) final; + void drop_back(const int count) final; + + int evaluated_points_size() const final; + + protected: + void correct_end_tangents() const final; + void ensure_base_cache() const final; +}; + +/* Proposed name to be different from DNA type. */ +class DCurve { + public: + blender::Vector splines; + + // bool is_2d; + + DCurve *copy(); + + // DCurve *copy(); + + void translate(const blender::float3 translation); + void transform(const blender::float4x4 &matrix); +}; + +DCurve *dcurve_from_dna_curve(const Curve &curve); \ No newline at end of file diff --git a/source/blender/blenkernel/CMakeLists.txt b/source/blender/blenkernel/CMakeLists.txt index 72c90c44a13..17639eaba85 100644 --- a/source/blender/blenkernel/CMakeLists.txt +++ b/source/blender/blenkernel/CMakeLists.txt @@ -118,10 +118,6 @@ set(SRC intern/data_transfer.c intern/deform.c intern/derived_curve.cc - intern/derived_curve_spline_base.cc - intern/derived_curve_spline_bezier.cc - intern/derived_curve_spline_nurbs.cc - intern/derived_curve_spline_poly.cc intern/displist.cc intern/displist_tangent.c intern/dynamicpaint.c @@ -247,6 +243,10 @@ set(SRC intern/softbody.c intern/sound.c intern/speaker.c + intern/spline_base.cc + intern/spline_bezier.cc + intern/spline_nurbs.cc + intern/spline_poly.cc intern/studiolight.c intern/subdiv.c intern/subdiv_ccg.c @@ -328,7 +328,7 @@ set(SRC BKE_customdata_file.h BKE_data_transfer.h BKE_deform.h - BKE_derived_curve.hh + BKE_spline.hh BKE_displist.h BKE_displist_tangent.h BKE_duplilist.h diff --git a/source/blender/blenkernel/intern/derived_curve.cc b/source/blender/blenkernel/intern/derived_curve.cc index 36b3dd2aff6..9f5f9143641 100644 --- a/source/blender/blenkernel/intern/derived_curve.cc +++ b/source/blender/blenkernel/intern/derived_curve.cc @@ -21,7 +21,7 @@ #include "DNA_curve_types.h" #include "BKE_curve.h" -#include "BKE_derived_curve.hh" +#include "BKE_spline.hh" using blender::Array; using blender::float3; diff --git a/source/blender/blenkernel/intern/derived_curve_spline_base.cc b/source/blender/blenkernel/intern/derived_curve_spline_base.cc deleted file mode 100644 index 3140a5d55ca..00000000000 --- a/source/blender/blenkernel/intern/derived_curve_spline_base.cc +++ /dev/null @@ -1,359 +0,0 @@ -/* - * 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. - */ - -#include "BLI_array.hh" -#include "BLI_listbase.h" -#include "BLI_span.hh" - -#include "DNA_curve_types.h" - -#include "BKE_derived_curve.hh" - -using blender::Array; -using blender::float3; -using blender::float4x4; -using blender::IndexRange; -using blender::MutableSpan; -using blender::Span; -using blender::Vector; - -/** - * Mark all caches for recomputation. This must be called after any operation that would - * change the generated positions, tangents, normals, mapping, etc. of the evaluated points. - */ -void Spline::mark_cache_invalid() -{ - base_cache_dirty_ = true; - tangent_cache_dirty_ = true; - normal_cache_dirty_ = true; - length_cache_dirty_ = true; -} - -int Spline::evaluated_edges_size() const -{ - const int points_len = this->evaluated_points_size(); - - return this->is_cyclic ? points_len : points_len - 1; -} - -float Spline::length() const -{ - return this->evaluated_lengths().last(); -} - -Span Spline::evaluated_positions() const -{ - this->ensure_base_cache(); - return evaluated_positions_cache_; -} - -int Spline::segments_size() const -{ - const int points_len = this->size(); - - return this->is_cyclic ? points_len : points_len - 1; -} - -/** - * Returns non-owning access to the cache of mappings from the evaluated points to - * the corresponing control points. Unless the spline is cyclic, the last control point - * index will never be included as an index. - */ -Span Spline::evaluated_mappings() const -{ - this->ensure_base_cache(); -#ifdef DEBUG - if (evaluated_mapping_cache_.last().control_point_index == this->size() - 1) { - BLI_assert(this->is_cyclic); - } -#endif - return evaluated_mapping_cache_; -} - -static void accumulate_lengths(Span positions, - const bool is_cyclic, - MutableSpan lengths) -{ - float length = 0.0f; - for (const int i : IndexRange(positions.size() - 1)) { - length += float3::distance(positions[i], positions[i + 1]); - lengths[i] = length; - } - if (is_cyclic) { - lengths.last() = length + float3::distance(positions.last(), positions.first()); - } -} - -/** - * 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, so it makes sense to cache it. - */ -Span Spline::evaluated_lengths() const -{ - if (!this->length_cache_dirty_) { - return evaluated_lengths_cache_; - } - - std::lock_guard lock{this->length_cache_mutex_}; - if (!this->length_cache_dirty_) { - return evaluated_lengths_cache_; - } - - const int total = this->evaluated_edges_size(); - this->evaluated_lengths_cache_.resize(total); - - Span positions = this->evaluated_positions(); - accumulate_lengths(positions, this->is_cyclic, this->evaluated_lengths_cache_); - - this->length_cache_dirty_ = false; - return evaluated_lengths_cache_; -} - -/* TODO: Optimize this along with the function below. */ -static float3 direction_bisect(const float3 &prev, const float3 &middle, const float3 &next) -{ - const float3 dir_prev = (middle - prev).normalized(); - const float3 dir_next = (next - middle).normalized(); - - return (dir_prev + dir_next).normalized(); -} - -static void calculate_tangents(Span positions, - const bool is_cyclic, - MutableSpan tangents) -{ - if (positions.size() == 1) { - return; - } - - for (const int i : IndexRange(1, positions.size() - 2)) { - tangents[i] = direction_bisect(positions[i - 1], positions[i], positions[i + 1]); - } - - if (is_cyclic) { - const float3 &second_to_last = positions[positions.size() - 2]; - const float3 &last = positions.last(); - const float3 &first = positions.first(); - const float3 &second = positions[1]; - tangents.first() = direction_bisect(last, first, second); - tangents.last() = direction_bisect(second_to_last, last, first); - } - else { - tangents.first() = (positions[1] - positions[0]).normalized(); - tangents.last() = (positions.last() - positions[positions.size() - 1]).normalized(); - } -} - -/** - * Return non-owning access to the direction of the curve at each evaluated point. - */ -Span Spline::evaluated_tangents() const -{ - if (!this->tangent_cache_dirty_) { - return evaluated_tangents_cache_; - } - - std::lock_guard lock{this->tangent_cache_mutex_}; - if (!this->tangent_cache_dirty_) { - return evaluated_tangents_cache_; - } - - const int total = this->evaluated_points_size(); - this->evaluated_tangents_cache_.resize(total); - - Span positions = this->evaluated_positions(); - - calculate_tangents(positions, this->is_cyclic, this->evaluated_tangents_cache_); - - this->correct_end_tangents(); - - this->tangent_cache_dirty_ = false; - return evaluated_tangents_cache_; -} - -static float3 initial_normal(const float3 first_tangent) -{ - /* TODO: Should be is "almost" zero. */ - if (first_tangent.is_zero()) { - return float3(0.0f, 0.0f, 1.0f); - } - - const float3 normal = float3::cross(first_tangent, float3(0.0f, 0.0f, 1.0f)); - if (!normal.is_zero()) { - return normal.normalized(); - } - - return float3::cross(first_tangent, float3(0.0f, 1.0f, 0.0f)).normalized(); -} - -static float3 rotate_around_axis(const float3 dir, const float3 axis, const float angle) -{ - BLI_ASSERT_UNIT_V3(axis); - const float3 scaled_axis = axis * float3::dot(dir, axis); - const float3 sub = dir - scaled_axis; - const float3 cross = float3::cross(sub, sub); - const float sin = std::sin(angle); - const float cos = std::cos(angle); - return (scaled_axis + sub * cos + cross * sin).normalized(); -} - -static float3 project_on_center_plane(const float3 vector, const float3 plane_normal) -{ - BLI_ASSERT_UNIT_V3(plane_normal); - const float distance = float3::dot(vector, plane_normal); - const float3 projection_vector = plane_normal * -distance; - return vector + projection_vector; -} - -static float3 propagate_normal(const float3 last_normal, - const float3 last_tangent, - const float3 current_tangent) -{ - const float angle = angle_normalized_v3v3(last_tangent, current_tangent); - - if (angle == 0.0f) { - return last_normal; - } - - const float3 axis = float3::cross(last_tangent, current_tangent).normalized(); - - const float3 new_normal = rotate_around_axis(last_normal, axis, angle); - - return project_on_center_plane(new_normal, current_tangent).normalized(); -} - -static void apply_rotation_gradient(Span tangents, - MutableSpan normals, - const float full_angle) -{ - - float remaining_rotation = full_angle; - float done_rotation = 0.0f; - for (const int i : IndexRange(1, normals.size() - 1)) { - if (angle_v3v3(tangents[i], tangents[i - 1]) < 0.001f) { - normals[i] = rotate_around_axis(normals[i], tangents[i], done_rotation); - } - else { - const float angle = remaining_rotation / (normals.size() - i); - normals[i] = rotate_around_axis(normals[i], tangents[i], angle + done_rotation); - remaining_rotation -= angle; - done_rotation += angle; - } - } -} - -static void make_normals_cyclic(Span tangents, MutableSpan normals) -{ - const float3 last_normal = propagate_normal(normals.last(), tangents.last(), tangents.first()); - - float angle = angle_normalized_v3v3(normals.first(), last_normal); - - const float3 cross = float3::cross(normals.first(), last_normal); - if (float3::dot(cross, tangents.first()) <= 0.0f) { - angle = -angle; - } - - apply_rotation_gradient(tangents, normals, -angle); -} - -/* This algorithm is a copy from animation nodes bezier normal calculation. - * TODO: Explore different methods, this also doesn't work right now. */ -static void calculate_normals_minimum_twist(Span tangents, - const bool is_cyclic, - MutableSpan normals) -{ - if (normals.size() == 1) { - normals.first() = float3(1.0f, 0.0f, 0.0f); - return; - } - - /* Start by calculating a simple normal for the first point. */ - normals[0] = initial_normal(tangents[0]); - - /* Then propogate that normal along the spline. */ - for (const int i : IndexRange(1, normals.size() - 1)) { - normals[i] = propagate_normal(normals[i - 1], tangents[i - 1], tangents[i]); - } - - if (is_cyclic) { - make_normals_cyclic(tangents, normals); - } -} - -static void calculate_normals_z_up(Span tangents, MutableSpan normals) -{ - for (const int i : normals.index_range()) { - normals[i] = float3::cross(tangents[i], float3(0.0f, 0.0f, 1.0f)).normalized(); - } -} - -/** - * 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. - */ -Span Spline::evaluated_normals() const -{ - if (!this->normal_cache_dirty_) { - return evaluated_normals_cache_; - } - - std::lock_guard lock{this->normal_cache_mutex_}; - if (!this->normal_cache_dirty_) { - return evaluated_normals_cache_; - } - - const int total = this->evaluated_points_size(); - this->evaluated_normals_cache_.resize(total); - - Span tangents = this->evaluated_tangents(); - switch (this->normal_mode) { - case NormalCalculationMode::Minimum: - calculate_normals_minimum_twist(tangents, is_cyclic, this->evaluated_normals_cache_); - break; - case NormalCalculationMode::ZUp: - calculate_normals_z_up(tangents, this->evaluated_normals_cache_); - break; - case NormalCalculationMode::Tangent: - // calculate_normals_tangent(tangents, this->evaluated_normals_cache_); - break; - } - - this->normal_cache_dirty_ = false; - return evaluated_normals_cache_; -} - -Spline::LookupResult Spline::lookup_evaluated_factor(const float factor) const -{ - return this->lookup_evaluated_length(this->length() * factor); -} - -/* TODO: Support extrapolation somehow. */ -Spline::LookupResult Spline::lookup_evaluated_length(const float length) const -{ - BLI_assert(length >= 0.0f && length <= this->length()); - - Span lengths = this->evaluated_lengths(); - - const float *offset = std::lower_bound(lengths.begin(), lengths.end(), length); - const int index = offset - lengths.begin(); - - const float previous_length = (index == 0) ? 0.0f : lengths[index - 1]; - const float factor = (length - previous_length) / (lengths[index] - previous_length); - - return LookupResult{index, factor}; -} diff --git a/source/blender/blenkernel/intern/derived_curve_spline_bezier.cc b/source/blender/blenkernel/intern/derived_curve_spline_bezier.cc deleted file mode 100644 index b0ff18116d1..00000000000 --- a/source/blender/blenkernel/intern/derived_curve_spline_bezier.cc +++ /dev/null @@ -1,378 +0,0 @@ -/* - * 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. - */ - -#include "BLI_array.hh" -#include "BLI_listbase.h" -#include "BLI_span.hh" - -#include "BKE_derived_curve.hh" - -using blender::Array; -using blender::float3; -using blender::float4x4; -using blender::IndexRange; -using blender::MutableSpan; -using blender::Span; -using blender::Vector; - -SplinePtr BezierSpline::copy() const -{ - SplinePtr new_spline = std::make_unique(*this); - - return new_spline; -} - -int BezierSpline::size() const -{ - const int size = this->positions_.size(); - BLI_assert(this->handle_types_start_.size() == size); - BLI_assert(this->handle_positions_start_.size() == size); - BLI_assert(this->handle_types_end_.size() == size); - BLI_assert(this->handle_positions_end_.size() == size); - BLI_assert(this->radii_.size() == size); - BLI_assert(this->tilts_.size() == size); - return size; -} - -int BezierSpline::resolution() const -{ - return this->resolution_u_; -} - -void BezierSpline::set_resolution(const int value) -{ - this->resolution_u_ = value; - this->mark_cache_invalid(); -} - -MutableSpan BezierSpline::positions() -{ - return this->positions_; -} -Span BezierSpline::positions() const -{ - return this->positions_; -} -MutableSpan BezierSpline::radii() -{ - return this->radii_; -} -Span BezierSpline::radii() const -{ - return this->radii_; -} -MutableSpan BezierSpline::tilts() -{ - return this->tilts_; -} -Span BezierSpline::tilts() const -{ - return this->tilts_; -} -Span BezierSpline::handle_types_start() const -{ - return this->handle_types_start_; -} -MutableSpan BezierSpline::handle_types_start() -{ - return this->handle_types_start_; -} -Span BezierSpline::handle_positions_start() const -{ - return this->handle_positions_start_; -} -MutableSpan BezierSpline::handle_positions_start() -{ - return this->handle_positions_start_; -} -Span BezierSpline::handle_types_end() const -{ - return this->handle_types_end_; -} -MutableSpan BezierSpline::handle_types_end() -{ - return this->handle_types_end_; -} -Span BezierSpline::handle_positions_end() const -{ - return this->handle_positions_end_; -} -MutableSpan BezierSpline::handle_positions_end() -{ - return this->handle_positions_end_; -} - -void BezierSpline::add_point(const float3 position, - const HandleType handle_type_start, - const float3 handle_position_start, - const HandleType handle_type_end, - const float3 handle_position_end, - const float radius, - const float tilt) -{ - handle_types_start_.append(handle_type_start); - handle_positions_start_.append(handle_position_start); - positions_.append(position); - handle_types_end_.append(handle_type_end); - handle_positions_end_.append(handle_position_end); - radii_.append(radius); - tilts_.append(tilt); -} - -void BezierSpline::drop_front(const int count) -{ - BLI_assert(this->size() - count > 0); - this->handle_types_start_.remove(0, count); - this->handle_positions_start_.remove(0, count); - this->positions_.remove(0, count); - this->handle_types_end_.remove(0, count); - this->handle_positions_end_.remove(0, count); - this->radii_.remove(0, count); - this->tilts_.remove(0, count); - this->mark_cache_invalid(); -} - -void BezierSpline::drop_back(const int count) -{ - const int new_size = this->size() - count; - BLI_assert(new_size > 0); - this->handle_types_start_.resize(new_size); - this->handle_positions_start_.resize(new_size); - this->positions_.resize(new_size); - this->handle_types_end_.resize(new_size); - this->handle_positions_end_.resize(new_size); - this->radii_.resize(new_size); - this->tilts_.resize(new_size); - this->mark_cache_invalid(); -} - -bool BezierSpline::point_is_sharp(const int index) const -{ - return ELEM(handle_types_start_[index], HandleType::Vector, HandleType::Free) || - ELEM(handle_types_end_[index], HandleType::Vector, HandleType::Free); -} - -bool BezierSpline::handle_start_is_automatic(const int index) const -{ - return ELEM(handle_types_start_[index], HandleType::Free, HandleType::Align); -} - -bool BezierSpline::handle_end_is_automatic(const int index) const -{ - return ELEM(handle_types_end_[index], HandleType::Free, HandleType::Align); -} - -void BezierSpline::move_control_point(const int index, const blender::float3 new_position) -{ - const float3 position_delta = new_position - positions_[index]; - if (!this->handle_start_is_automatic(index)) { - handle_positions_start_[index] += position_delta; - } - if (!this->handle_end_is_automatic(index)) { - handle_positions_end_[index] += position_delta; - } - positions_[index] = new_position; -} - -bool BezierSpline::segment_is_vector(const int index) const -{ - if (index == this->size() - 1) { - BLI_assert(this->is_cyclic); - return this->handle_types_end_.last() == HandleType::Vector && - this->handle_types_start_.first() == HandleType::Vector; - } - return this->handle_types_end_[index] == HandleType::Vector && - this->handle_types_start_[index + 1] == HandleType::Vector; -} - -int BezierSpline::evaluated_points_size() const -{ - BLI_assert(this->size() > 0); -#ifndef DEBUG - if (!this->base_cache_dirty_) { - /* In a non-debug build, assume that the cache's size has not changed, and that any operation - * that would cause the cache to change its length would also mark the cache dirty. This is - * checked at the end of this function in a debug build. */ - return this->evaluated_positions_cache_.size(); - } -#endif - - int total_len = 0; - for (const int i : IndexRange(this->size() - 1)) { - if (this->segment_is_vector(i)) { - total_len += 1; - } - else { - total_len += this->resolution_u_; - } - } - - if (this->is_cyclic) { - if (segment_is_vector(this->size() - 1)) { - total_len++; - } - else { - total_len += this->resolution_u_; - } - } - else { - /* Since evaulating the bezier doesn't add the final point's position, - * it must be added manually in the non-cyclic case. */ - total_len++; - } - - /* Assert that the cache has the correct length in debug mode. */ - if (!this->base_cache_dirty_) { - BLI_assert(this->evaluated_positions_cache_.size() == total_len); - } - - return total_len; -} - -/** - * 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 BezierSpline::correct_end_tangents() const -{ - MutableSpan tangents(this->evaluated_tangents_cache_); - - if (handle_positions_start_.first() != positions_.first()) { - tangents.first() = (positions_.first() - handle_positions_start_.first()).normalized(); - } - if (handle_positions_end_.last() != positions_.last()) { - tangents.last() = (handle_positions_end_.last() - positions_.last()).normalized(); - } -} - -static void bezier_forward_difference_3d(const float3 &point_0, - const float3 &point_1, - const float3 &point_2, - const float3 &point_3, - MutableSpan result) -{ - const float len = static_cast(result.size()); - const float len_squared = len * len; - const float len_cubed = len_squared * len; - BLI_assert(len > 0.0f); - - const float3 rt1 = 3.0f * (point_1 - point_0) / len; - const float3 rt2 = 3.0f * (point_0 - 2.0f * point_1 + point_2) / len_squared; - const float3 rt3 = (point_3 - point_0 + 3.0f * (point_1 - point_2)) / len_cubed; - - float3 q0 = point_0; - float3 q1 = rt1 + rt2 + rt3; - float3 q2 = 2.0f * rt2 + 6.0f * rt3; - float3 q3 = 6.0f * rt3; - for (const int i : result.index_range()) { - result[i] = q0; - q0 += q1; - q1 += q2; - q2 += q3; - } -} - -static void evaluate_segment_mapping(Span evaluated_positions, - MutableSpan mappings, - const int index) -{ - float length = 0.0f; - mappings[0] = PointMapping{index, 0.0f}; - for (const int i : IndexRange(1, mappings.size() - 1)) { - length += float3::distance(evaluated_positions[i - 1], evaluated_positions[i]); - mappings[i] = PointMapping{index, length}; - } - - /* To get the factors instead of the accumulated lengths, divide the mapping factors by the - * accumulated length. */ - if (length != 0.0f) { - for (PointMapping &mapping : mappings) { - mapping.factor /= length; - } - } -} - -void BezierSpline::evaluate_bezier_segment(const int index, - const int next_index, - int &offset, - MutableSpan positions, - MutableSpan mappings) const -{ - if (this->segment_is_vector(index)) { - positions[offset] = positions_[index]; - mappings[offset] = PointMapping{index, 0.0f}; - offset++; - } - else { - bezier_forward_difference_3d(this->positions_[index], - this->handle_positions_end_[index], - this->handle_positions_start_[next_index], - this->positions_[next_index], - positions.slice(offset, this->resolution_u_)); - evaluate_segment_mapping(positions.slice(offset, this->resolution_u_), - mappings.slice(offset, this->resolution_u_), - index); - offset += this->resolution_u_; - } -} - -void BezierSpline::evaluate_bezier_position_and_mapping(MutableSpan positions, - MutableSpan mappings) const -{ - /* TODO: It would also be possible to store an array of offsets to facilitate parallelism here, - * maybe it is worth it? */ - int offset = 0; - for (const int i : IndexRange(this->size() - 1)) { - this->evaluate_bezier_segment(i, i + 1, offset, positions, mappings); - } - - const int i_last = this->size() - 1; - if (this->is_cyclic) { - this->evaluate_bezier_segment(i_last, 0, offset, positions, mappings); - } - else { - /* Since evaulating the bezier doesn't add the final point's position, - * it must be added manually in the non-cyclic case. */ - positions[offset] = this->positions_.last(); - mappings[offset] = PointMapping{i_last - 1, 1.0f}; - offset++; - } - - BLI_assert(offset == positions.size()); -} - -void BezierSpline::ensure_base_cache() const -{ - if (!this->base_cache_dirty_) { - return; - } - - std::lock_guard lock{this->base_cache_mutex_}; - if (!this->base_cache_dirty_) { - return; - } - - const int total = this->evaluated_points_size(); - this->evaluated_positions_cache_.resize(total); - this->evaluated_mapping_cache_.resize(total); - - this->evaluate_bezier_position_and_mapping(this->evaluated_positions_cache_, - this->evaluated_mapping_cache_); - - this->base_cache_dirty_ = false; -} \ No newline at end of file diff --git a/source/blender/blenkernel/intern/derived_curve_spline_nurbs.cc b/source/blender/blenkernel/intern/derived_curve_spline_nurbs.cc deleted file mode 100644 index 0691dfdd84c..00000000000 --- a/source/blender/blenkernel/intern/derived_curve_spline_nurbs.cc +++ /dev/null @@ -1,451 +0,0 @@ -/* - * 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. - */ - -#include "BLI_array.hh" -#include "BLI_listbase.h" -#include "BLI_span.hh" -#include "BLI_virtual_array.hh" - -#include "BKE_attribute_math.hh" -#include "BKE_derived_curve.hh" - -using blender::Array; -using blender::float3; -using blender::float4x4; -using blender::IndexRange; -using blender::MutableSpan; -using blender::Span; -using blender::Vector; - -SplinePtr NURBSpline::copy() const -{ - SplinePtr new_spline = std::make_unique(*this); - - return new_spline; -} - -int NURBSpline::size() const -{ - const int size = this->positions_.size(); - BLI_assert(this->radii_.size() == size); - BLI_assert(this->tilts_.size() == size); - BLI_assert(this->weights_.size() == size); - return size; -} - -int NURBSpline::resolution() const -{ - return this->resolution_u_; -} - -void NURBSpline::set_resolution(const int value) -{ - this->resolution_u_ = value; - this->mark_cache_invalid(); -} - -uint8_t NURBSpline::order() const -{ - return this->order_; -} - -void NURBSpline::set_order(const uint8_t value) -{ - /* TODO: Check the spline length. */ - BLI_assert(value >= 2 && value <= 6); - this->order_ = value; -} - -void NURBSpline::add_point(const float3 position, - const float radius, - const float tilt, - const float weight) -{ - this->positions_.append(position); - this->radii_.append(radius); - this->tilts_.append(tilt); - this->weights_.append(weight); - this->knots_dirty_ = true; -} - -void NURBSpline::drop_front(const int count) -{ - BLI_assert(this->size() - count > 0); - this->positions_.remove(0, count); - this->radii_.remove(0, count); - this->tilts_.remove(0, count); - this->weights_.remove(0, count); - this->mark_cache_invalid(); -} - -void NURBSpline::drop_back(const int count) -{ - const int new_size = this->size() - count; - BLI_assert(new_size > 0); - this->positions_.resize(new_size); - this->radii_.resize(new_size); - this->tilts_.resize(new_size); - this->weights_.resize(new_size); - this->mark_cache_invalid(); -} - -MutableSpan NURBSpline::positions() -{ - return this->positions_; -} -Span NURBSpline::positions() const -{ - return this->positions_; -} -MutableSpan NURBSpline::radii() -{ - return this->radii_; -} -Span NURBSpline::radii() const -{ - return this->radii_; -} -MutableSpan NURBSpline::tilts() -{ - return this->tilts_; -} -Span NURBSpline::tilts() const -{ - return this->tilts_; -} -MutableSpan NURBSpline::weights() -{ - return this->weights_; -} -Span NURBSpline::weights() const -{ - return this->weights_; -} - -int NURBSpline::evaluated_points_size() const -{ - return this->resolution_u_ * this->segments_size(); -} - -void NURBSpline::correct_end_tangents() const -{ -} - -bool NURBSpline::check_valid_size_and_order() const -{ - if (this->size() < this->order_) { - return false; - } - - if (!this->is_cyclic && this->knots_mode == KnotsMode::Bezier) { - if (this->order_ == 4) { - if (this->size() < 5) { - return false; - } - } - else if (this->order_ != 3) { - return false; - } - } - - return true; -} - -int NURBSpline::knots_size() const -{ - const int size = this->size() + this->order_; - return this->is_cyclic ? size + this->order_ - 1 : size; -} - -void NURBSpline::calculate_knots() const -{ - const KnotsMode mode = this->knots_mode; - const int length = this->size(); - const int order = this->order_; - - this->knots_.resize(this->knots_size()); - - MutableSpan knots = this->knots_; - - if (mode == NURBSpline::KnotsMode::Normal || this->is_cyclic) { - for (const int i : knots.index_range()) { - knots[i] = static_cast(i); - } - } - else if (mode == NURBSpline::KnotsMode::EndPoint) { - float k = 0.0f; - for (const int i : IndexRange(1, knots.size())) { - knots[i - 1] = k; - if (i >= order && i <= length) { - k += 1.0f; - } - } - } - else if (mode == NURBSpline::KnotsMode::Bezier) { - BLI_assert(ELEM(order, 3, 4)); - if (order == 3) { - float k = 0.6f; - for (const int i : knots.index_range()) { - if (i >= order && i <= length) { - k += 0.5f; - } - knots[i] = std::floor(k); - } - } - else { - float k = 0.34f; - for (const int i : knots.index_range()) { - knots[i] = std::floor(k); - k += 1.0f / 3.0f; - } - } - } - - if (this->is_cyclic) { - const int b = length + order - 1; - if (order > 2) { - for (const int i : IndexRange(1, order - 2)) { - if (knots[b] != knots[b - i]) { - if (i == order - 1) { - knots[length + order - 2] += 1.0f; - break; - } - } - } - } - - int c = order; - for (int i = b; i < this->knots_size(); i++) { - knots[i] = knots[i - 1] + (knots[c] - knots[c - 1]); - c--; - } - } -} - -Span NURBSpline::knots() const -{ - if (!this->knots_dirty_) { - BLI_assert(this->knots_.size() == this->size() + this->order_); - return this->knots_; - } - - std::lock_guard lock{this->knots_mutex_}; - if (!this->knots_dirty_) { - BLI_assert(this->knots_.size() == this->size() + this->order_); - return this->knots_; - } - - this->calculate_knots(); - - this->base_cache_dirty_ = false; - - return this->knots_; -} - -/* TODO: Better variables names, simplify logic once it works. */ -static void nurb_basis(const float parameter, - const int points_len, - const int order, - Span knots, - MutableSpan basis, - int &start, - int &end) -{ - /* Clamp parameter due to floating point inaccuracy. TODO: Look into using doubles. */ - const float t = std::clamp(parameter, knots[0], knots[points_len + order - 1]); - - int i1 = 0; - int i2 = 0; - for (int i = 0; i < points_len + order - 1; i++) { - if ((knots[i] != knots[i + 1]) && (t >= knots[i]) && (t <= knots[i + 1])) { - basis[i] = 1.0f; - i1 = std::max(i - order - 1, 0); - i2 = i; - i++; - while (i < points_len + order - 1) { - basis[i] = 0.0f; - i++; - } - break; - } - basis[i] = 0.0f; - } - basis[points_len + order - 1] = 0.0f; - - for (int i_order = 2; i_order <= order; i_order++) { - if (i2 + i_order >= points_len + order) { - i2 = points_len + order - 1 - i_order; - } - for (int i = i1; i <= i2; i++) { - float new_basis = 0.0f; - if (basis[i] != 0.0f) { - new_basis += ((t - knots[i]) * basis[i]) / (knots[i + i_order - 1] - knots[i]); - } - - if (basis[i + 1] != 0.0f) { - new_basis += ((knots[i + i_order] - t) * basis[i + 1]) / - (knots[i + i_order] - knots[i + 1]); - } - - basis[i] = new_basis; - } - } - - start = 1000; - end = 0; - - for (int i = i1; i <= i2; i++) { - if (basis[i] > 0.0f) { - end = i; - if (start == 1000) { - start = i; - } - } - } -} - -void NURBSpline::calculate_weights() const -{ - if (!this->weights_dirty_) { - return; - } - - std::lock_guard lock{this->weights_mutex_}; - if (!this->weights_dirty_) { - return; - } - - const int evaluated_len = this->evaluated_points_size(); - this->weight_cache_.resize(evaluated_len); - - const int points_len = this->size(); - const int order = this->order(); - Span control_weights = this->weights(); - Span knots = this->knots(); - - MutableSpan weights = this->weight_cache_; - - const float start = knots[order - 1]; - const float end = this->is_cyclic ? knots[points_len + order - 1] : knots[points_len]; - const float step = (end - start) / (evaluated_len - (this->is_cyclic ? 0 : 1)); - - Array sums(points_len); - Array basis(this->knots_size()); - - float u = start; - for (const int i : IndexRange(evaluated_len)) { - int j_start; - int j_end; - nurb_basis( - u, points_len + (this->is_cyclic ? order - 1 : 0), order, knots, basis, j_start, j_end); - BLI_assert(j_end - j_start < order); - - /* Calculate sums. */ - float sum_total = 0.0f; - for (const int j : IndexRange(j_end - j_start + 1)) { - const int point_index = (j_start + j) % points_len; - - sums[j] = basis[j_start + j] * control_weights[point_index]; - sum_total += sums[j]; - } - if (sum_total != 0.0f) { - for (const int j : IndexRange(j_end - j_start + 1)) { - sums[j] /= sum_total; - } - } - - weights[i].start_index = j_start; - weights[i].weights.clear(); - for (const int j : IndexRange(j_end - j_start + 1)) { - weights[i].weights.append(sums[j]); - } - - u += step; - } - - this->weights_dirty_ = false; -} - -template -void interpolate_to_evaluated_points_impl(Span weights, - const blender::VArray &old_values, - MutableSpan r_values) -{ - const int points_len = old_values.size(); - BLI_assert(r_values.size() == weights.size()); - blender::attribute_math::DefaultMixer mixer(r_values); - - for (const int i : r_values.index_range()) { - Span point_weights = weights[i].weights; - const int start_index = weights[i].start_index; - - for (const int j : IndexRange(point_weights.size())) { - const int point_index = (start_index + j) % points_len; - mixer.mix_in(i, old_values[point_index], point_weights[j]); - } - } - - mixer.finalize(); -} - -blender::fn::GVArrayPtr NURBSpline::interpolate_to_evaluated_points( - const blender::fn::GVArray &source_data) const -{ - this->calculate_weights(); - Span weights = this->weight_cache_; - - blender::fn::GVArrayPtr new_varray; - blender::attribute_math::convert_to_static_type(source_data.type(), [&](auto dummy) { - using T = decltype(dummy); - if constexpr (!std::is_void_v>) { - Array values(this->evaluated_points_size()); - interpolate_to_evaluated_points_impl(weights, source_data.typed(), values); - new_varray = std::make_unique>>( - std::move(values)); - } - }); - - return new_varray; -} - -void NURBSpline::ensure_base_cache() const -{ - if (!this->base_cache_dirty_) { - return; - } - - std::lock_guard lock{this->base_cache_mutex_}; - if (!this->base_cache_dirty_) { - return; - } - - const int total = this->evaluated_points_size(); - this->evaluated_positions_cache_.resize(total); - this->evaluated_mapping_cache_.resize(total); - - blender::fn::GVArray_For_Span positions_varray(this->positions_.as_span()); - blender::fn::GVArrayPtr evaluated_positions_varray = this->interpolate_to_evaluated_points( - positions_varray); - - Span evaluated_positions = - evaluated_positions_varray->typed()->get_internal_span(); - - for (const int i : IndexRange(total)) { - this->evaluated_positions_cache_[i] = evaluated_positions[i]; - } - - this->base_cache_dirty_ = false; -} diff --git a/source/blender/blenkernel/intern/derived_curve_spline_poly.cc b/source/blender/blenkernel/intern/derived_curve_spline_poly.cc deleted file mode 100644 index 23e88192da2..00000000000 --- a/source/blender/blenkernel/intern/derived_curve_spline_poly.cc +++ /dev/null @@ -1,143 +0,0 @@ -/* - * 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. - */ - -#include "BLI_array.hh" -#include "BLI_listbase.h" -#include "BLI_span.hh" - -#include "BKE_curve.h" -#include "BKE_derived_curve.hh" - -using blender::Array; -using blender::float3; -using blender::float4x4; -using blender::IndexRange; -using blender::MutableSpan; -using blender::Span; -using blender::Vector; - -SplinePtr PolySpline::copy() const -{ - SplinePtr new_spline = std::make_unique(*this); - - return new_spline; -} - -int PolySpline::size() const -{ - const int size = this->positions_.size(); - BLI_assert(this->radii_.size() == size); - BLI_assert(this->tilts_.size() == size); - return size; -} - -int PolySpline::resolution() const -{ - return 1; -} - -void PolySpline::set_resolution(const int UNUSED(value)) -{ - /* Poly curve has no resolution, there is just one evaluated point per control point. */ -} - -void PolySpline::add_point(const float3 position, const float radius, const float tilt) -{ - this->positions_.append(position); - this->radii_.append(radius); - this->tilts_.append(tilt); -} - -void PolySpline::drop_front(const int count) -{ - BLI_assert(this->size() - count > 0); - this->positions_.remove(0, count); - this->radii_.remove(0, count); - this->tilts_.remove(0, count); - this->mark_cache_invalid(); -} - -void PolySpline::drop_back(const int count) -{ - const int new_size = this->size() - count; - BLI_assert(new_size > 0); - this->positions_.resize(new_size); - this->radii_.resize(new_size); - this->tilts_.resize(new_size); - this->mark_cache_invalid(); -} - -MutableSpan PolySpline::positions() -{ - return this->positions_; -} -Span PolySpline::positions() const -{ - return this->positions_; -} -MutableSpan PolySpline::radii() -{ - return this->radii_; -} -Span PolySpline::radii() const -{ - return this->radii_; -} -MutableSpan PolySpline::tilts() -{ - return this->tilts_; -} -Span PolySpline::tilts() const -{ - return this->tilts_; -} - -int PolySpline::evaluated_points_size() const -{ - return this->size(); -} - -void PolySpline::correct_end_tangents() const -{ -} - -/* TODO: Consider refactoring to avoid copying and "mapping" for poly splines. */ -void PolySpline::ensure_base_cache() const -{ - if (!this->base_cache_dirty_) { - return; - } - - std::lock_guard lock{this->base_cache_mutex_}; - if (!this->base_cache_dirty_) { - return; - } - - const int total = this->evaluated_points_size(); - this->evaluated_positions_cache_.resize(total); - this->evaluated_mapping_cache_.resize(total); - - MutableSpan positions = this->evaluated_positions_cache_.as_mutable_span(); - MutableSpan mappings = this->evaluated_mapping_cache_.as_mutable_span(); - - for (const int i : positions.index_range()) { - positions[i] = this->positions_[i]; - mappings[i].control_point_index = i; - mappings[i].factor = 0.0f; - } - - this->base_cache_dirty_ = false; -} diff --git a/source/blender/blenkernel/intern/displist.cc b/source/blender/blenkernel/intern/displist.cc index 3f3ffee19be..0b960add98d 100644 --- a/source/blender/blenkernel/intern/displist.cc +++ b/source/blender/blenkernel/intern/displist.cc @@ -44,7 +44,6 @@ #include "BKE_anim_path.h" #include "BKE_curve.h" -#include "BKE_derived_curve.hh" #include "BKE_displist.h" #include "BKE_font.h" #include "BKE_geometry_set.hh" @@ -56,6 +55,7 @@ #include "BKE_mesh.h" #include "BKE_modifier.h" #include "BKE_object.h" +#include "BKE_spline.hh" #include "BLI_sys_types.h" // for intptr_t support diff --git a/source/blender/blenkernel/intern/geometry_component_curve.cc b/source/blender/blenkernel/intern/geometry_component_curve.cc index a1f77c36cc0..a37b1da3847 100644 --- a/source/blender/blenkernel/intern/geometry_component_curve.cc +++ b/source/blender/blenkernel/intern/geometry_component_curve.cc @@ -14,7 +14,7 @@ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ -#include "BKE_derived_curve.hh" +#include "BKE_spline.hh" #include "BKE_attribute_access.hh" #include "BKE_attribute_math.hh" @@ -192,7 +192,8 @@ class BuiltinSplineAttributeProvider final : public BuiltinAttributeProvider { return false; } - bool try_create(GeometryComponent &UNUSED(component)) const final + bool try_create(GeometryComponent &UNUSED(component), + const AttributeInit &UNUSED(initializer)) const final { return false; } @@ -327,7 +328,8 @@ class BuiltinPointAttributeProvider final : public BuiltinAttributeProvider { return false; } - bool try_create(GeometryComponent &UNUSED(component)) const final + bool try_create(GeometryComponent &UNUSED(component), + const AttributeInit &UNUSED(initializer)) const final { return false; } diff --git a/source/blender/blenkernel/intern/geometry_set.cc b/source/blender/blenkernel/intern/geometry_set.cc index d52f41c6bbd..1493eedf01c 100644 --- a/source/blender/blenkernel/intern/geometry_set.cc +++ b/source/blender/blenkernel/intern/geometry_set.cc @@ -18,13 +18,13 @@ #include "BKE_attribute.h" #include "BKE_attribute_access.hh" -#include "BKE_derived_curve.hh" #include "BKE_geometry_set.hh" #include "BKE_lib_id.h" #include "BKE_mesh.h" #include "BKE_mesh_wrapper.h" #include "BKE_modifier.h" #include "BKE_pointcloud.h" +#include "BKE_spline.hh" #include "BKE_volume.h" #include "DNA_collection_types.h" diff --git a/source/blender/blenkernel/intern/spline_base.cc b/source/blender/blenkernel/intern/spline_base.cc new file mode 100644 index 00000000000..88ac8aa1a30 --- /dev/null +++ b/source/blender/blenkernel/intern/spline_base.cc @@ -0,0 +1,359 @@ +/* + * 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. + */ + +#include "BLI_array.hh" +#include "BLI_listbase.h" +#include "BLI_span.hh" + +#include "DNA_curve_types.h" + +#include "BKE_spline.hh" + +using blender::Array; +using blender::float3; +using blender::float4x4; +using blender::IndexRange; +using blender::MutableSpan; +using blender::Span; +using blender::Vector; + +/** + * Mark all caches for recomputation. This must be called after any operation that would + * change the generated positions, tangents, normals, mapping, etc. of the evaluated points. + */ +void Spline::mark_cache_invalid() +{ + base_cache_dirty_ = true; + tangent_cache_dirty_ = true; + normal_cache_dirty_ = true; + length_cache_dirty_ = true; +} + +int Spline::evaluated_edges_size() const +{ + const int points_len = this->evaluated_points_size(); + + return this->is_cyclic ? points_len : points_len - 1; +} + +float Spline::length() const +{ + return this->evaluated_lengths().last(); +} + +Span Spline::evaluated_positions() const +{ + this->ensure_base_cache(); + return evaluated_positions_cache_; +} + +int Spline::segments_size() const +{ + const int points_len = this->size(); + + return this->is_cyclic ? points_len : points_len - 1; +} + +/** + * Returns non-owning access to the cache of mappings from the evaluated points to + * the corresponing control points. Unless the spline is cyclic, the last control point + * index will never be included as an index. + */ +Span Spline::evaluated_mappings() const +{ + this->ensure_base_cache(); +#ifdef DEBUG + if (evaluated_mapping_cache_.last().control_point_index == this->size() - 1) { + BLI_assert(this->is_cyclic); + } +#endif + return evaluated_mapping_cache_; +} + +static void accumulate_lengths(Span positions, + const bool is_cyclic, + MutableSpan lengths) +{ + float length = 0.0f; + for (const int i : IndexRange(positions.size() - 1)) { + length += float3::distance(positions[i], positions[i + 1]); + lengths[i] = length; + } + if (is_cyclic) { + lengths.last() = length + float3::distance(positions.last(), positions.first()); + } +} + +/** + * 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, so it makes sense to cache it. + */ +Span Spline::evaluated_lengths() const +{ + if (!this->length_cache_dirty_) { + return evaluated_lengths_cache_; + } + + std::lock_guard lock{this->length_cache_mutex_}; + if (!this->length_cache_dirty_) { + return evaluated_lengths_cache_; + } + + const int total = this->evaluated_edges_size(); + this->evaluated_lengths_cache_.resize(total); + + Span positions = this->evaluated_positions(); + accumulate_lengths(positions, this->is_cyclic, this->evaluated_lengths_cache_); + + this->length_cache_dirty_ = false; + return evaluated_lengths_cache_; +} + +/* TODO: Optimize this along with the function below. */ +static float3 direction_bisect(const float3 &prev, const float3 &middle, const float3 &next) +{ + const float3 dir_prev = (middle - prev).normalized(); + const float3 dir_next = (next - middle).normalized(); + + return (dir_prev + dir_next).normalized(); +} + +static void calculate_tangents(Span positions, + const bool is_cyclic, + MutableSpan tangents) +{ + if (positions.size() == 1) { + return; + } + + for (const int i : IndexRange(1, positions.size() - 2)) { + tangents[i] = direction_bisect(positions[i - 1], positions[i], positions[i + 1]); + } + + if (is_cyclic) { + const float3 &second_to_last = positions[positions.size() - 2]; + const float3 &last = positions.last(); + const float3 &first = positions.first(); + const float3 &second = positions[1]; + tangents.first() = direction_bisect(last, first, second); + tangents.last() = direction_bisect(second_to_last, last, first); + } + else { + tangents.first() = (positions[1] - positions[0]).normalized(); + tangents.last() = (positions.last() - positions[positions.size() - 1]).normalized(); + } +} + +/** + * Return non-owning access to the direction of the curve at each evaluated point. + */ +Span Spline::evaluated_tangents() const +{ + if (!this->tangent_cache_dirty_) { + return evaluated_tangents_cache_; + } + + std::lock_guard lock{this->tangent_cache_mutex_}; + if (!this->tangent_cache_dirty_) { + return evaluated_tangents_cache_; + } + + const int total = this->evaluated_points_size(); + this->evaluated_tangents_cache_.resize(total); + + Span positions = this->evaluated_positions(); + + calculate_tangents(positions, this->is_cyclic, this->evaluated_tangents_cache_); + + this->correct_end_tangents(); + + this->tangent_cache_dirty_ = false; + return evaluated_tangents_cache_; +} + +static float3 initial_normal(const float3 first_tangent) +{ + /* TODO: Should be is "almost" zero. */ + if (first_tangent.is_zero()) { + return float3(0.0f, 0.0f, 1.0f); + } + + const float3 normal = float3::cross(first_tangent, float3(0.0f, 0.0f, 1.0f)); + if (!normal.is_zero()) { + return normal.normalized(); + } + + return float3::cross(first_tangent, float3(0.0f, 1.0f, 0.0f)).normalized(); +} + +static float3 rotate_around_axis(const float3 dir, const float3 axis, const float angle) +{ + BLI_ASSERT_UNIT_V3(axis); + const float3 scaled_axis = axis * float3::dot(dir, axis); + const float3 sub = dir - scaled_axis; + const float3 cross = float3::cross(sub, sub); + const float sin = std::sin(angle); + const float cos = std::cos(angle); + return (scaled_axis + sub * cos + cross * sin).normalized(); +} + +static float3 project_on_center_plane(const float3 vector, const float3 plane_normal) +{ + BLI_ASSERT_UNIT_V3(plane_normal); + const float distance = float3::dot(vector, plane_normal); + const float3 projection_vector = plane_normal * -distance; + return vector + projection_vector; +} + +static float3 propagate_normal(const float3 last_normal, + const float3 last_tangent, + const float3 current_tangent) +{ + const float angle = angle_normalized_v3v3(last_tangent, current_tangent); + + if (angle == 0.0f) { + return last_normal; + } + + const float3 axis = float3::cross(last_tangent, current_tangent).normalized(); + + const float3 new_normal = rotate_around_axis(last_normal, axis, angle); + + return project_on_center_plane(new_normal, current_tangent).normalized(); +} + +static void apply_rotation_gradient(Span tangents, + MutableSpan normals, + const float full_angle) +{ + + float remaining_rotation = full_angle; + float done_rotation = 0.0f; + for (const int i : IndexRange(1, normals.size() - 1)) { + if (angle_v3v3(tangents[i], tangents[i - 1]) < 0.001f) { + normals[i] = rotate_around_axis(normals[i], tangents[i], done_rotation); + } + else { + const float angle = remaining_rotation / (normals.size() - i); + normals[i] = rotate_around_axis(normals[i], tangents[i], angle + done_rotation); + remaining_rotation -= angle; + done_rotation += angle; + } + } +} + +static void make_normals_cyclic(Span tangents, MutableSpan normals) +{ + const float3 last_normal = propagate_normal(normals.last(), tangents.last(), tangents.first()); + + float angle = angle_normalized_v3v3(normals.first(), last_normal); + + const float3 cross = float3::cross(normals.first(), last_normal); + if (float3::dot(cross, tangents.first()) <= 0.0f) { + angle = -angle; + } + + apply_rotation_gradient(tangents, normals, -angle); +} + +/* This algorithm is a copy from animation nodes bezier normal calculation. + * TODO: Explore different methods, this also doesn't work right now. */ +static void calculate_normals_minimum_twist(Span tangents, + const bool is_cyclic, + MutableSpan normals) +{ + if (normals.size() == 1) { + normals.first() = float3(1.0f, 0.0f, 0.0f); + return; + } + + /* Start by calculating a simple normal for the first point. */ + normals[0] = initial_normal(tangents[0]); + + /* Then propogate that normal along the spline. */ + for (const int i : IndexRange(1, normals.size() - 1)) { + normals[i] = propagate_normal(normals[i - 1], tangents[i - 1], tangents[i]); + } + + if (is_cyclic) { + make_normals_cyclic(tangents, normals); + } +} + +static void calculate_normals_z_up(Span tangents, MutableSpan normals) +{ + for (const int i : normals.index_range()) { + normals[i] = float3::cross(tangents[i], float3(0.0f, 0.0f, 1.0f)).normalized(); + } +} + +/** + * 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. + */ +Span Spline::evaluated_normals() const +{ + if (!this->normal_cache_dirty_) { + return evaluated_normals_cache_; + } + + std::lock_guard lock{this->normal_cache_mutex_}; + if (!this->normal_cache_dirty_) { + return evaluated_normals_cache_; + } + + const int total = this->evaluated_points_size(); + this->evaluated_normals_cache_.resize(total); + + Span tangents = this->evaluated_tangents(); + switch (this->normal_mode) { + case NormalCalculationMode::Minimum: + calculate_normals_minimum_twist(tangents, is_cyclic, this->evaluated_normals_cache_); + break; + case NormalCalculationMode::ZUp: + calculate_normals_z_up(tangents, this->evaluated_normals_cache_); + break; + case NormalCalculationMode::Tangent: + // calculate_normals_tangent(tangents, this->evaluated_normals_cache_); + break; + } + + this->normal_cache_dirty_ = false; + return evaluated_normals_cache_; +} + +Spline::LookupResult Spline::lookup_evaluated_factor(const float factor) const +{ + return this->lookup_evaluated_length(this->length() * factor); +} + +/* TODO: Support extrapolation somehow. */ +Spline::LookupResult Spline::lookup_evaluated_length(const float length) const +{ + BLI_assert(length >= 0.0f && length <= this->length()); + + Span lengths = this->evaluated_lengths(); + + const float *offset = std::lower_bound(lengths.begin(), lengths.end(), length); + const int index = offset - lengths.begin(); + + const float previous_length = (index == 0) ? 0.0f : lengths[index - 1]; + const float factor = (length - previous_length) / (lengths[index] - previous_length); + + return LookupResult{index, factor}; +} diff --git a/source/blender/blenkernel/intern/spline_bezier.cc b/source/blender/blenkernel/intern/spline_bezier.cc new file mode 100644 index 00000000000..b8f3717c464 --- /dev/null +++ b/source/blender/blenkernel/intern/spline_bezier.cc @@ -0,0 +1,378 @@ +/* + * 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. + */ + +#include "BLI_array.hh" +#include "BLI_listbase.h" +#include "BLI_span.hh" + +#include "BKE_spline.hh" + +using blender::Array; +using blender::float3; +using blender::float4x4; +using blender::IndexRange; +using blender::MutableSpan; +using blender::Span; +using blender::Vector; + +SplinePtr BezierSpline::copy() const +{ + SplinePtr new_spline = std::make_unique(*this); + + return new_spline; +} + +int BezierSpline::size() const +{ + const int size = this->positions_.size(); + BLI_assert(this->handle_types_start_.size() == size); + BLI_assert(this->handle_positions_start_.size() == size); + BLI_assert(this->handle_types_end_.size() == size); + BLI_assert(this->handle_positions_end_.size() == size); + BLI_assert(this->radii_.size() == size); + BLI_assert(this->tilts_.size() == size); + return size; +} + +int BezierSpline::resolution() const +{ + return this->resolution_u_; +} + +void BezierSpline::set_resolution(const int value) +{ + this->resolution_u_ = value; + this->mark_cache_invalid(); +} + +MutableSpan BezierSpline::positions() +{ + return this->positions_; +} +Span BezierSpline::positions() const +{ + return this->positions_; +} +MutableSpan BezierSpline::radii() +{ + return this->radii_; +} +Span BezierSpline::radii() const +{ + return this->radii_; +} +MutableSpan BezierSpline::tilts() +{ + return this->tilts_; +} +Span BezierSpline::tilts() const +{ + return this->tilts_; +} +Span BezierSpline::handle_types_start() const +{ + return this->handle_types_start_; +} +MutableSpan BezierSpline::handle_types_start() +{ + return this->handle_types_start_; +} +Span BezierSpline::handle_positions_start() const +{ + return this->handle_positions_start_; +} +MutableSpan BezierSpline::handle_positions_start() +{ + return this->handle_positions_start_; +} +Span BezierSpline::handle_types_end() const +{ + return this->handle_types_end_; +} +MutableSpan BezierSpline::handle_types_end() +{ + return this->handle_types_end_; +} +Span BezierSpline::handle_positions_end() const +{ + return this->handle_positions_end_; +} +MutableSpan BezierSpline::handle_positions_end() +{ + return this->handle_positions_end_; +} + +void BezierSpline::add_point(const float3 position, + const HandleType handle_type_start, + const float3 handle_position_start, + const HandleType handle_type_end, + const float3 handle_position_end, + const float radius, + const float tilt) +{ + handle_types_start_.append(handle_type_start); + handle_positions_start_.append(handle_position_start); + positions_.append(position); + handle_types_end_.append(handle_type_end); + handle_positions_end_.append(handle_position_end); + radii_.append(radius); + tilts_.append(tilt); +} + +void BezierSpline::drop_front(const int count) +{ + BLI_assert(this->size() - count > 0); + this->handle_types_start_.remove(0, count); + this->handle_positions_start_.remove(0, count); + this->positions_.remove(0, count); + this->handle_types_end_.remove(0, count); + this->handle_positions_end_.remove(0, count); + this->radii_.remove(0, count); + this->tilts_.remove(0, count); + this->mark_cache_invalid(); +} + +void BezierSpline::drop_back(const int count) +{ + const int new_size = this->size() - count; + BLI_assert(new_size > 0); + this->handle_types_start_.resize(new_size); + this->handle_positions_start_.resize(new_size); + this->positions_.resize(new_size); + this->handle_types_end_.resize(new_size); + this->handle_positions_end_.resize(new_size); + this->radii_.resize(new_size); + this->tilts_.resize(new_size); + this->mark_cache_invalid(); +} + +bool BezierSpline::point_is_sharp(const int index) const +{ + return ELEM(handle_types_start_[index], HandleType::Vector, HandleType::Free) || + ELEM(handle_types_end_[index], HandleType::Vector, HandleType::Free); +} + +bool BezierSpline::handle_start_is_automatic(const int index) const +{ + return ELEM(handle_types_start_[index], HandleType::Free, HandleType::Align); +} + +bool BezierSpline::handle_end_is_automatic(const int index) const +{ + return ELEM(handle_types_end_[index], HandleType::Free, HandleType::Align); +} + +void BezierSpline::move_control_point(const int index, const blender::float3 new_position) +{ + const float3 position_delta = new_position - positions_[index]; + if (!this->handle_start_is_automatic(index)) { + handle_positions_start_[index] += position_delta; + } + if (!this->handle_end_is_automatic(index)) { + handle_positions_end_[index] += position_delta; + } + positions_[index] = new_position; +} + +bool BezierSpline::segment_is_vector(const int index) const +{ + if (index == this->size() - 1) { + BLI_assert(this->is_cyclic); + return this->handle_types_end_.last() == HandleType::Vector && + this->handle_types_start_.first() == HandleType::Vector; + } + return this->handle_types_end_[index] == HandleType::Vector && + this->handle_types_start_[index + 1] == HandleType::Vector; +} + +int BezierSpline::evaluated_points_size() const +{ + BLI_assert(this->size() > 0); +#ifndef DEBUG + if (!this->base_cache_dirty_) { + /* In a non-debug build, assume that the cache's size has not changed, and that any operation + * that would cause the cache to change its length would also mark the cache dirty. This is + * checked at the end of this function in a debug build. */ + return this->evaluated_positions_cache_.size(); + } +#endif + + int total_len = 0; + for (const int i : IndexRange(this->size() - 1)) { + if (this->segment_is_vector(i)) { + total_len += 1; + } + else { + total_len += this->resolution_u_; + } + } + + if (this->is_cyclic) { + if (segment_is_vector(this->size() - 1)) { + total_len++; + } + else { + total_len += this->resolution_u_; + } + } + else { + /* Since evaulating the bezier doesn't add the final point's position, + * it must be added manually in the non-cyclic case. */ + total_len++; + } + + /* Assert that the cache has the correct length in debug mode. */ + if (!this->base_cache_dirty_) { + BLI_assert(this->evaluated_positions_cache_.size() == total_len); + } + + return total_len; +} + +/** + * 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 BezierSpline::correct_end_tangents() const +{ + MutableSpan tangents(this->evaluated_tangents_cache_); + + if (handle_positions_start_.first() != positions_.first()) { + tangents.first() = (positions_.first() - handle_positions_start_.first()).normalized(); + } + if (handle_positions_end_.last() != positions_.last()) { + tangents.last() = (handle_positions_end_.last() - positions_.last()).normalized(); + } +} + +static void bezier_forward_difference_3d(const float3 &point_0, + const float3 &point_1, + const float3 &point_2, + const float3 &point_3, + MutableSpan result) +{ + const float len = static_cast(result.size()); + const float len_squared = len * len; + const float len_cubed = len_squared * len; + BLI_assert(len > 0.0f); + + const float3 rt1 = 3.0f * (point_1 - point_0) / len; + const float3 rt2 = 3.0f * (point_0 - 2.0f * point_1 + point_2) / len_squared; + const float3 rt3 = (point_3 - point_0 + 3.0f * (point_1 - point_2)) / len_cubed; + + float3 q0 = point_0; + float3 q1 = rt1 + rt2 + rt3; + float3 q2 = 2.0f * rt2 + 6.0f * rt3; + float3 q3 = 6.0f * rt3; + for (const int i : result.index_range()) { + result[i] = q0; + q0 += q1; + q1 += q2; + q2 += q3; + } +} + +static void evaluate_segment_mapping(Span evaluated_positions, + MutableSpan mappings, + const int index) +{ + float length = 0.0f; + mappings[0] = PointMapping{index, 0.0f}; + for (const int i : IndexRange(1, mappings.size() - 1)) { + length += float3::distance(evaluated_positions[i - 1], evaluated_positions[i]); + mappings[i] = PointMapping{index, length}; + } + + /* To get the factors instead of the accumulated lengths, divide the mapping factors by the + * accumulated length. */ + if (length != 0.0f) { + for (PointMapping &mapping : mappings) { + mapping.factor /= length; + } + } +} + +void BezierSpline::evaluate_bezier_segment(const int index, + const int next_index, + int &offset, + MutableSpan positions, + MutableSpan mappings) const +{ + if (this->segment_is_vector(index)) { + positions[offset] = positions_[index]; + mappings[offset] = PointMapping{index, 0.0f}; + offset++; + } + else { + bezier_forward_difference_3d(this->positions_[index], + this->handle_positions_end_[index], + this->handle_positions_start_[next_index], + this->positions_[next_index], + positions.slice(offset, this->resolution_u_)); + evaluate_segment_mapping(positions.slice(offset, this->resolution_u_), + mappings.slice(offset, this->resolution_u_), + index); + offset += this->resolution_u_; + } +} + +void BezierSpline::evaluate_bezier_position_and_mapping(MutableSpan positions, + MutableSpan mappings) const +{ + /* TODO: It would also be possible to store an array of offsets to facilitate parallelism here, + * maybe it is worth it? */ + int offset = 0; + for (const int i : IndexRange(this->size() - 1)) { + this->evaluate_bezier_segment(i, i + 1, offset, positions, mappings); + } + + const int i_last = this->size() - 1; + if (this->is_cyclic) { + this->evaluate_bezier_segment(i_last, 0, offset, positions, mappings); + } + else { + /* Since evaulating the bezier doesn't add the final point's position, + * it must be added manually in the non-cyclic case. */ + positions[offset] = this->positions_.last(); + mappings[offset] = PointMapping{i_last - 1, 1.0f}; + offset++; + } + + BLI_assert(offset == positions.size()); +} + +void BezierSpline::ensure_base_cache() const +{ + if (!this->base_cache_dirty_) { + return; + } + + std::lock_guard lock{this->base_cache_mutex_}; + if (!this->base_cache_dirty_) { + return; + } + + const int total = this->evaluated_points_size(); + this->evaluated_positions_cache_.resize(total); + this->evaluated_mapping_cache_.resize(total); + + this->evaluate_bezier_position_and_mapping(this->evaluated_positions_cache_, + this->evaluated_mapping_cache_); + + this->base_cache_dirty_ = false; +} \ No newline at end of file diff --git a/source/blender/blenkernel/intern/spline_nurbs.cc b/source/blender/blenkernel/intern/spline_nurbs.cc new file mode 100644 index 00000000000..a03a0a23ca2 --- /dev/null +++ b/source/blender/blenkernel/intern/spline_nurbs.cc @@ -0,0 +1,451 @@ +/* + * 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. + */ + +#include "BLI_array.hh" +#include "BLI_listbase.h" +#include "BLI_span.hh" +#include "BLI_virtual_array.hh" + +#include "BKE_attribute_math.hh" +#include "BKE_spline.hh" + +using blender::Array; +using blender::float3; +using blender::float4x4; +using blender::IndexRange; +using blender::MutableSpan; +using blender::Span; +using blender::Vector; + +SplinePtr NURBSpline::copy() const +{ + SplinePtr new_spline = std::make_unique(*this); + + return new_spline; +} + +int NURBSpline::size() const +{ + const int size = this->positions_.size(); + BLI_assert(this->radii_.size() == size); + BLI_assert(this->tilts_.size() == size); + BLI_assert(this->weights_.size() == size); + return size; +} + +int NURBSpline::resolution() const +{ + return this->resolution_u_; +} + +void NURBSpline::set_resolution(const int value) +{ + this->resolution_u_ = value; + this->mark_cache_invalid(); +} + +uint8_t NURBSpline::order() const +{ + return this->order_; +} + +void NURBSpline::set_order(const uint8_t value) +{ + /* TODO: Check the spline length. */ + BLI_assert(value >= 2 && value <= 6); + this->order_ = value; +} + +void NURBSpline::add_point(const float3 position, + const float radius, + const float tilt, + const float weight) +{ + this->positions_.append(position); + this->radii_.append(radius); + this->tilts_.append(tilt); + this->weights_.append(weight); + this->knots_dirty_ = true; +} + +void NURBSpline::drop_front(const int count) +{ + BLI_assert(this->size() - count > 0); + this->positions_.remove(0, count); + this->radii_.remove(0, count); + this->tilts_.remove(0, count); + this->weights_.remove(0, count); + this->mark_cache_invalid(); +} + +void NURBSpline::drop_back(const int count) +{ + const int new_size = this->size() - count; + BLI_assert(new_size > 0); + this->positions_.resize(new_size); + this->radii_.resize(new_size); + this->tilts_.resize(new_size); + this->weights_.resize(new_size); + this->mark_cache_invalid(); +} + +MutableSpan NURBSpline::positions() +{ + return this->positions_; +} +Span NURBSpline::positions() const +{ + return this->positions_; +} +MutableSpan NURBSpline::radii() +{ + return this->radii_; +} +Span NURBSpline::radii() const +{ + return this->radii_; +} +MutableSpan NURBSpline::tilts() +{ + return this->tilts_; +} +Span NURBSpline::tilts() const +{ + return this->tilts_; +} +MutableSpan NURBSpline::weights() +{ + return this->weights_; +} +Span NURBSpline::weights() const +{ + return this->weights_; +} + +int NURBSpline::evaluated_points_size() const +{ + return this->resolution_u_ * this->segments_size(); +} + +void NURBSpline::correct_end_tangents() const +{ +} + +bool NURBSpline::check_valid_size_and_order() const +{ + if (this->size() < this->order_) { + return false; + } + + if (!this->is_cyclic && this->knots_mode == KnotsMode::Bezier) { + if (this->order_ == 4) { + if (this->size() < 5) { + return false; + } + } + else if (this->order_ != 3) { + return false; + } + } + + return true; +} + +int NURBSpline::knots_size() const +{ + const int size = this->size() + this->order_; + return this->is_cyclic ? size + this->order_ - 1 : size; +} + +void NURBSpline::calculate_knots() const +{ + const KnotsMode mode = this->knots_mode; + const int length = this->size(); + const int order = this->order_; + + this->knots_.resize(this->knots_size()); + + MutableSpan knots = this->knots_; + + if (mode == NURBSpline::KnotsMode::Normal || this->is_cyclic) { + for (const int i : knots.index_range()) { + knots[i] = static_cast(i); + } + } + else if (mode == NURBSpline::KnotsMode::EndPoint) { + float k = 0.0f; + for (const int i : IndexRange(1, knots.size())) { + knots[i - 1] = k; + if (i >= order && i <= length) { + k += 1.0f; + } + } + } + else if (mode == NURBSpline::KnotsMode::Bezier) { + BLI_assert(ELEM(order, 3, 4)); + if (order == 3) { + float k = 0.6f; + for (const int i : knots.index_range()) { + if (i >= order && i <= length) { + k += 0.5f; + } + knots[i] = std::floor(k); + } + } + else { + float k = 0.34f; + for (const int i : knots.index_range()) { + knots[i] = std::floor(k); + k += 1.0f / 3.0f; + } + } + } + + if (this->is_cyclic) { + const int b = length + order - 1; + if (order > 2) { + for (const int i : IndexRange(1, order - 2)) { + if (knots[b] != knots[b - i]) { + if (i == order - 1) { + knots[length + order - 2] += 1.0f; + break; + } + } + } + } + + int c = order; + for (int i = b; i < this->knots_size(); i++) { + knots[i] = knots[i - 1] + (knots[c] - knots[c - 1]); + c--; + } + } +} + +Span NURBSpline::knots() const +{ + if (!this->knots_dirty_) { + BLI_assert(this->knots_.size() == this->size() + this->order_); + return this->knots_; + } + + std::lock_guard lock{this->knots_mutex_}; + if (!this->knots_dirty_) { + BLI_assert(this->knots_.size() == this->size() + this->order_); + return this->knots_; + } + + this->calculate_knots(); + + this->base_cache_dirty_ = false; + + return this->knots_; +} + +/* TODO: Better variables names, simplify logic once it works. */ +static void nurb_basis(const float parameter, + const int points_len, + const int order, + Span knots, + MutableSpan basis, + int &start, + int &end) +{ + /* Clamp parameter due to floating point inaccuracy. TODO: Look into using doubles. */ + const float t = std::clamp(parameter, knots[0], knots[points_len + order - 1]); + + int i1 = 0; + int i2 = 0; + for (int i = 0; i < points_len + order - 1; i++) { + if ((knots[i] != knots[i + 1]) && (t >= knots[i]) && (t <= knots[i + 1])) { + basis[i] = 1.0f; + i1 = std::max(i - order - 1, 0); + i2 = i; + i++; + while (i < points_len + order - 1) { + basis[i] = 0.0f; + i++; + } + break; + } + basis[i] = 0.0f; + } + basis[points_len + order - 1] = 0.0f; + + for (int i_order = 2; i_order <= order; i_order++) { + if (i2 + i_order >= points_len + order) { + i2 = points_len + order - 1 - i_order; + } + for (int i = i1; i <= i2; i++) { + float new_basis = 0.0f; + if (basis[i] != 0.0f) { + new_basis += ((t - knots[i]) * basis[i]) / (knots[i + i_order - 1] - knots[i]); + } + + if (basis[i + 1] != 0.0f) { + new_basis += ((knots[i + i_order] - t) * basis[i + 1]) / + (knots[i + i_order] - knots[i + 1]); + } + + basis[i] = new_basis; + } + } + + start = 1000; + end = 0; + + for (int i = i1; i <= i2; i++) { + if (basis[i] > 0.0f) { + end = i; + if (start == 1000) { + start = i; + } + } + } +} + +void NURBSpline::calculate_weights() const +{ + if (!this->weights_dirty_) { + return; + } + + std::lock_guard lock{this->weights_mutex_}; + if (!this->weights_dirty_) { + return; + } + + const int evaluated_len = this->evaluated_points_size(); + this->weight_cache_.resize(evaluated_len); + + const int points_len = this->size(); + const int order = this->order(); + Span control_weights = this->weights(); + Span knots = this->knots(); + + MutableSpan weights = this->weight_cache_; + + const float start = knots[order - 1]; + const float end = this->is_cyclic ? knots[points_len + order - 1] : knots[points_len]; + const float step = (end - start) / (evaluated_len - (this->is_cyclic ? 0 : 1)); + + Array sums(points_len); + Array basis(this->knots_size()); + + float u = start; + for (const int i : IndexRange(evaluated_len)) { + int j_start; + int j_end; + nurb_basis( + u, points_len + (this->is_cyclic ? order - 1 : 0), order, knots, basis, j_start, j_end); + BLI_assert(j_end - j_start < order); + + /* Calculate sums. */ + float sum_total = 0.0f; + for (const int j : IndexRange(j_end - j_start + 1)) { + const int point_index = (j_start + j) % points_len; + + sums[j] = basis[j_start + j] * control_weights[point_index]; + sum_total += sums[j]; + } + if (sum_total != 0.0f) { + for (const int j : IndexRange(j_end - j_start + 1)) { + sums[j] /= sum_total; + } + } + + weights[i].start_index = j_start; + weights[i].weights.clear(); + for (const int j : IndexRange(j_end - j_start + 1)) { + weights[i].weights.append(sums[j]); + } + + u += step; + } + + this->weights_dirty_ = false; +} + +template +void interpolate_to_evaluated_points_impl(Span weights, + const blender::VArray &old_values, + MutableSpan r_values) +{ + const int points_len = old_values.size(); + BLI_assert(r_values.size() == weights.size()); + blender::attribute_math::DefaultMixer mixer(r_values); + + for (const int i : r_values.index_range()) { + Span point_weights = weights[i].weights; + const int start_index = weights[i].start_index; + + for (const int j : IndexRange(point_weights.size())) { + const int point_index = (start_index + j) % points_len; + mixer.mix_in(i, old_values[point_index], point_weights[j]); + } + } + + mixer.finalize(); +} + +blender::fn::GVArrayPtr NURBSpline::interpolate_to_evaluated_points( + const blender::fn::GVArray &source_data) const +{ + this->calculate_weights(); + Span weights = this->weight_cache_; + + blender::fn::GVArrayPtr new_varray; + blender::attribute_math::convert_to_static_type(source_data.type(), [&](auto dummy) { + using T = decltype(dummy); + if constexpr (!std::is_void_v>) { + Array values(this->evaluated_points_size()); + interpolate_to_evaluated_points_impl(weights, source_data.typed(), values); + new_varray = std::make_unique>>( + std::move(values)); + } + }); + + return new_varray; +} + +void NURBSpline::ensure_base_cache() const +{ + if (!this->base_cache_dirty_) { + return; + } + + std::lock_guard lock{this->base_cache_mutex_}; + if (!this->base_cache_dirty_) { + return; + } + + const int total = this->evaluated_points_size(); + this->evaluated_positions_cache_.resize(total); + this->evaluated_mapping_cache_.resize(total); + + blender::fn::GVArray_For_Span positions_varray(this->positions_.as_span()); + blender::fn::GVArrayPtr evaluated_positions_varray = this->interpolate_to_evaluated_points( + positions_varray); + + Span evaluated_positions = + evaluated_positions_varray->typed()->get_internal_span(); + + for (const int i : IndexRange(total)) { + this->evaluated_positions_cache_[i] = evaluated_positions[i]; + } + + this->base_cache_dirty_ = false; +} diff --git a/source/blender/blenkernel/intern/spline_poly.cc b/source/blender/blenkernel/intern/spline_poly.cc new file mode 100644 index 00000000000..aa9935cb055 --- /dev/null +++ b/source/blender/blenkernel/intern/spline_poly.cc @@ -0,0 +1,143 @@ +/* + * 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. + */ + +#include "BLI_array.hh" +#include "BLI_listbase.h" +#include "BLI_span.hh" + +#include "BKE_curve.h" +#include "BKE_spline.hh" + +using blender::Array; +using blender::float3; +using blender::float4x4; +using blender::IndexRange; +using blender::MutableSpan; +using blender::Span; +using blender::Vector; + +SplinePtr PolySpline::copy() const +{ + SplinePtr new_spline = std::make_unique(*this); + + return new_spline; +} + +int PolySpline::size() const +{ + const int size = this->positions_.size(); + BLI_assert(this->radii_.size() == size); + BLI_assert(this->tilts_.size() == size); + return size; +} + +int PolySpline::resolution() const +{ + return 1; +} + +void PolySpline::set_resolution(const int UNUSED(value)) +{ + /* Poly curve has no resolution, there is just one evaluated point per control point. */ +} + +void PolySpline::add_point(const float3 position, const float radius, const float tilt) +{ + this->positions_.append(position); + this->radii_.append(radius); + this->tilts_.append(tilt); +} + +void PolySpline::drop_front(const int count) +{ + BLI_assert(this->size() - count > 0); + this->positions_.remove(0, count); + this->radii_.remove(0, count); + this->tilts_.remove(0, count); + this->mark_cache_invalid(); +} + +void PolySpline::drop_back(const int count) +{ + const int new_size = this->size() - count; + BLI_assert(new_size > 0); + this->positions_.resize(new_size); + this->radii_.resize(new_size); + this->tilts_.resize(new_size); + this->mark_cache_invalid(); +} + +MutableSpan PolySpline::positions() +{ + return this->positions_; +} +Span PolySpline::positions() const +{ + return this->positions_; +} +MutableSpan PolySpline::radii() +{ + return this->radii_; +} +Span PolySpline::radii() const +{ + return this->radii_; +} +MutableSpan PolySpline::tilts() +{ + return this->tilts_; +} +Span PolySpline::tilts() const +{ + return this->tilts_; +} + +int PolySpline::evaluated_points_size() const +{ + return this->size(); +} + +void PolySpline::correct_end_tangents() const +{ +} + +/* TODO: Consider refactoring to avoid copying and "mapping" for poly splines. */ +void PolySpline::ensure_base_cache() const +{ + if (!this->base_cache_dirty_) { + return; + } + + std::lock_guard lock{this->base_cache_mutex_}; + if (!this->base_cache_dirty_) { + return; + } + + const int total = this->evaluated_points_size(); + this->evaluated_positions_cache_.resize(total); + this->evaluated_mapping_cache_.resize(total); + + MutableSpan positions = this->evaluated_positions_cache_.as_mutable_span(); + MutableSpan mappings = this->evaluated_mapping_cache_.as_mutable_span(); + + for (const int i : positions.index_range()) { + positions[i] = this->positions_[i]; + mappings[i].control_point_index = i; + mappings[i].factor = 0.0f; + } + + this->base_cache_dirty_ = false; +} diff --git a/source/blender/nodes/geometry/nodes/node_geo_curve_sample_points.cc b/source/blender/nodes/geometry/nodes/node_geo_curve_sample_points.cc index dd3b94cfcff..080cfdaf5c5 100644 --- a/source/blender/nodes/geometry/nodes/node_geo_curve_sample_points.cc +++ b/source/blender/nodes/geometry/nodes/node_geo_curve_sample_points.cc @@ -14,8 +14,8 @@ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ -#include "BKE_derived_curve.hh" #include "BKE_pointcloud.h" +#include "BKE_spline.hh" #include "UI_interface.h" #include "UI_resources.h" diff --git a/source/blender/nodes/geometry/nodes/node_geo_curve_to_mesh.cc b/source/blender/nodes/geometry/nodes/node_geo_curve_to_mesh.cc index 19a5f0660ca..619ee71e387 100644 --- a/source/blender/nodes/geometry/nodes/node_geo_curve_to_mesh.cc +++ b/source/blender/nodes/geometry/nodes/node_geo_curve_to_mesh.cc @@ -21,8 +21,8 @@ #include "DNA_mesh_types.h" #include "DNA_meshdata_types.h" -#include "BKE_derived_curve.hh" #include "BKE_mesh.h" +#include "BKE_spline.hh" #include "UI_interface.h" #include "UI_resources.h" diff --git a/source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc b/source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc index 01c9eac2036..60b0e648e01 100644 --- a/source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc +++ b/source/blender/nodes/geometry/nodes/node_geo_curve_trim.cc @@ -14,7 +14,7 @@ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ -#include "BKE_derived_curve.hh" +#include "BKE_spline.hh" #include "UI_interface.h" #include "UI_resources.h" diff --git a/source/blender/nodes/geometry/nodes/node_geo_join_geometry.cc b/source/blender/nodes/geometry/nodes/node_geo_join_geometry.cc index 536cb446140..4f994a75a0e 100644 --- a/source/blender/nodes/geometry/nodes/node_geo_join_geometry.cc +++ b/source/blender/nodes/geometry/nodes/node_geo_join_geometry.cc @@ -14,10 +14,10 @@ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ -#include "BKE_derived_curve.hh" #include "BKE_mesh.h" #include "BKE_mesh_runtime.h" #include "BKE_pointcloud.h" +#include "BKE_spline.hh" #include "DNA_mesh_types.h" #include "DNA_meshdata_types.h" diff --git a/source/blender/nodes/geometry/nodes/node_geo_object_info.cc b/source/blender/nodes/geometry/nodes/node_geo_object_info.cc index 9764940115e..2f339aa761c 100644 --- a/source/blender/nodes/geometry/nodes/node_geo_object_info.cc +++ b/source/blender/nodes/geometry/nodes/node_geo_object_info.cc @@ -17,7 +17,7 @@ #include "DNA_curve_types.h" #include "DNA_object_types.h" -#include "BKE_derived_curve.hh" +#include "BKE_spline.hh" #include "BLI_math_matrix.h" diff --git a/source/blender/nodes/geometry/nodes/node_geo_transform.cc b/source/blender/nodes/geometry/nodes/node_geo_transform.cc index 9fc8e6daccc..68e1a08a774 100644 --- a/source/blender/nodes/geometry/nodes/node_geo_transform.cc +++ b/source/blender/nodes/geometry/nodes/node_geo_transform.cc @@ -23,8 +23,8 @@ #include "DNA_pointcloud_types.h" #include "DNA_volume_types.h" -#include "BKE_derived_curve.hh" #include "BKE_mesh.h" +#include "BKE_spline.hh" #include "BKE_volume.h" #include "DEG_depsgraph_query.h" -- cgit v1.2.3