Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat (limited to 'source/blender/blenkernel/intern/spline_bezier.cc')
-rw-r--r--source/blender/blenkernel/intern/spline_bezier.cc478
1 files changed, 478 insertions, 0 deletions
diff --git a/source/blender/blenkernel/intern/spline_bezier.cc b/source/blender/blenkernel/intern/spline_bezier.cc
new file mode 100644
index 00000000000..4981f441190
--- /dev/null
+++ b/source/blender/blenkernel/intern/spline_bezier.cc
@@ -0,0 +1,478 @@
+/*
+ * 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_span.hh"
+#include "BLI_task.hh"
+
+#include "BKE_spline.hh"
+
+using blender::Array;
+using blender::float3;
+using blender::IndexRange;
+using blender::MutableSpan;
+using blender::Span;
+
+SplinePtr BezierSpline::copy() const
+{
+ return std::make_unique<BezierSpline>(*this);
+}
+
+int BezierSpline::size() const
+{
+ const int size = positions_.size();
+ BLI_assert(size == handle_types_left_.size());
+ BLI_assert(size == handle_positions_left_.size());
+ BLI_assert(size == handle_types_right_.size());
+ BLI_assert(size == handle_positions_right_.size());
+ BLI_assert(size == radii_.size());
+ BLI_assert(size == tilts_.size());
+ return size;
+}
+
+int BezierSpline::resolution() const
+{
+ return resolution_;
+}
+
+void BezierSpline::set_resolution(const int value)
+{
+ BLI_assert(value > 0);
+ resolution_ = value;
+ this->mark_cache_invalid();
+}
+
+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_left_.append(handle_type_start);
+ handle_positions_left_.append(handle_position_start);
+ positions_.append(position);
+ handle_types_right_.append(handle_type_end);
+ handle_positions_right_.append(handle_position_end);
+ radii_.append(radius);
+ tilts_.append(tilt);
+ this->mark_cache_invalid();
+}
+
+MutableSpan<float3> BezierSpline::positions()
+{
+ return positions_;
+}
+Span<float3> BezierSpline::positions() const
+{
+ return positions_;
+}
+MutableSpan<float> BezierSpline::radii()
+{
+ return radii_;
+}
+Span<float> BezierSpline::radii() const
+{
+ return radii_;
+}
+MutableSpan<float> BezierSpline::tilts()
+{
+ return tilts_;
+}
+Span<float> BezierSpline::tilts() const
+{
+ return tilts_;
+}
+Span<BezierSpline::HandleType> BezierSpline::handle_types_left() const
+{
+ return handle_types_left_;
+}
+MutableSpan<BezierSpline::HandleType> BezierSpline::handle_types_left()
+{
+ return handle_types_left_;
+}
+Span<float3> BezierSpline::handle_positions_left() const
+{
+ return handle_positions_left_;
+}
+MutableSpan<float3> BezierSpline::handle_positions_left()
+{
+ return handle_positions_left_;
+}
+Span<BezierSpline::HandleType> BezierSpline::handle_types_right() const
+{
+ return handle_types_right_;
+}
+MutableSpan<BezierSpline::HandleType> BezierSpline::handle_types_right()
+{
+ return handle_types_right_;
+}
+Span<float3> BezierSpline::handle_positions_right() const
+{
+ return handle_positions_right_;
+}
+MutableSpan<float3> BezierSpline::handle_positions_right()
+{
+ return handle_positions_right_;
+}
+
+void BezierSpline::translate(const blender::float3 &translation)
+{
+ for (float3 &position : this->positions()) {
+ position += translation;
+ }
+ for (float3 &handle_position : this->handle_positions_left()) {
+ handle_position += translation;
+ }
+ for (float3 &handle_position : this->handle_positions_right()) {
+ handle_position += translation;
+ }
+ this->mark_cache_invalid();
+}
+
+void BezierSpline::transform(const blender::float4x4 &matrix)
+{
+ for (float3 &position : this->positions()) {
+ position = matrix * position;
+ }
+ for (float3 &handle_position : this->handle_positions_left()) {
+ handle_position = matrix * handle_position;
+ }
+ for (float3 &handle_position : this->handle_positions_right()) {
+ handle_position = matrix * handle_position;
+ }
+ this->mark_cache_invalid();
+}
+
+bool BezierSpline::point_is_sharp(const int index) const
+{
+ return ELEM(handle_types_left_[index], HandleType::Vector, HandleType::Free) ||
+ ELEM(handle_types_right_[index], HandleType::Vector, HandleType::Free);
+}
+
+bool BezierSpline::segment_is_vector(const int index) const
+{
+ if (index == this->size() - 1) {
+ BLI_assert(is_cyclic_);
+ return handle_types_right_.last() == HandleType::Vector &&
+ handle_types_left_.first() == HandleType::Vector;
+ }
+ return handle_types_right_[index] == HandleType::Vector &&
+ handle_types_left_[index + 1] == HandleType::Vector;
+}
+
+void BezierSpline::mark_cache_invalid()
+{
+ offset_cache_dirty_ = true;
+ position_cache_dirty_ = true;
+ mapping_cache_dirty_ = true;
+ tangent_cache_dirty_ = true;
+ normal_cache_dirty_ = true;
+ length_cache_dirty_ = true;
+}
+
+int BezierSpline::evaluated_points_size() const
+{
+ const int points_len = this->size();
+ BLI_assert(points_len > 0);
+
+ const int last_offset = this->control_point_offsets().last();
+ if (is_cyclic_ && points_len > 1) {
+ return last_offset + (this->segment_is_vector(points_len - 1) ? 0 : resolution_);
+ }
+
+ return last_offset + 1;
+}
+
+/**
+ * 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
+{
+ if (is_cyclic_) {
+ return;
+ }
+
+ MutableSpan<float3> tangents(evaluated_tangents_cache_);
+
+ if (handle_positions_left_.first() != positions_.first()) {
+ tangents.first() = (positions_.first() - handle_positions_left_.first()).normalized();
+ }
+ if (handle_positions_right_.last() != positions_.last()) {
+ tangents.last() = (handle_positions_right_.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<float3> result)
+{
+ BLI_assert(result.size() > 0);
+ const float inv_len = 1.0f / static_cast<float>(result.size());
+ const float inv_len_squared = inv_len * inv_len;
+ const float inv_len_cubed = inv_len_squared * inv_len;
+
+ const float3 rt1 = 3.0f * (point_1 - point_0) * inv_len;
+ const float3 rt2 = 3.0f * (point_0 - 2.0f * point_1 + point_2) * inv_len_squared;
+ const float3 rt3 = (point_3 - point_0 + 3.0f * (point_1 - point_2)) * inv_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;
+ }
+}
+
+void BezierSpline::evaluate_bezier_segment(const int index,
+ const int next_index,
+ MutableSpan<float3> positions) const
+{
+ if (this->segment_is_vector(index)) {
+ BLI_assert(positions.size() == 1);
+ positions.first() = positions_[index];
+ }
+ else {
+ bezier_forward_difference_3d(positions_[index],
+ handle_positions_right_[index],
+ handle_positions_left_[next_index],
+ positions_[next_index],
+ positions);
+ }
+}
+
+/**
+ * Returns access to a cache of offsets into the evaluated point array for each control point.
+ * This is important because while most control point edges generate the number of edges specified
+ * by the resolution, vector segments only generate one edge.
+ */
+Span<int> BezierSpline::control_point_offsets() const
+{
+ if (!offset_cache_dirty_) {
+ return offset_cache_;
+ }
+
+ std::lock_guard lock{offset_cache_mutex_};
+ if (!offset_cache_dirty_) {
+ return offset_cache_;
+ }
+
+ const int points_len = this->size();
+ offset_cache_.resize(points_len);
+
+ MutableSpan<int> offsets = offset_cache_;
+
+ int offset = 0;
+ for (const int i : IndexRange(points_len - 1)) {
+ offsets[i] = offset;
+ offset += this->segment_is_vector(i) ? 1 : resolution_;
+ }
+ offsets.last() = offset;
+
+ offset_cache_dirty_ = false;
+ return offsets;
+}
+
+/**
+ * Returns non-owning access to an array of values containing the information necessary to
+ * interpolate values from the original control points to evaluated points. The control point
+ * index is the integer part of each value, and the factor used for interpolating to the next
+ * control point is the remaining factional part.
+ */
+Span<float> BezierSpline::evaluated_mappings() const
+{
+ if (!mapping_cache_dirty_) {
+ return evaluated_mapping_cache_;
+ }
+
+ std::lock_guard lock{mapping_cache_mutex_};
+ if (!mapping_cache_dirty_) {
+ return evaluated_mapping_cache_;
+ }
+
+ const int size = this->size();
+ const int eval_size = this->evaluated_points_size();
+ evaluated_mapping_cache_.resize(eval_size);
+ MutableSpan<float> mappings = evaluated_mapping_cache_;
+
+ if (eval_size == 1) {
+ mappings.first() = 0.0f;
+ mapping_cache_dirty_ = false;
+ return mappings;
+ }
+
+ Span<int> offsets = this->control_point_offsets();
+ Span<float> lengths = this->evaluated_lengths();
+
+ /* Subtract one from the index into the lengths array to get the length
+ * at the start point rather than the length at the end of the edge. */
+
+ const float first_segment_len = lengths[offsets[1] - 1];
+ for (const int eval_index : IndexRange(0, offsets[1])) {
+ const float point_len = eval_index == 0 ? 0.0f : lengths[eval_index - 1];
+ const float length_factor = (first_segment_len == 0.0f) ? 0.0f : 1.0f / first_segment_len;
+
+ mappings[eval_index] = point_len * length_factor;
+ }
+
+ const int grain_size = std::max(512 / resolution_, 1);
+ blender::parallel_for(IndexRange(1, size - 2), grain_size, [&](IndexRange range) {
+ for (const int i : range) {
+ const float segment_start_len = lengths[offsets[i] - 1];
+ const float segment_end_len = lengths[offsets[i + 1] - 1];
+ const float segment_len = segment_end_len - segment_start_len;
+ const float length_factor = (segment_len == 0.0f) ? 0.0f : 1.0f / segment_len;
+
+ for (const int eval_index : IndexRange(offsets[i], offsets[i + 1] - offsets[i])) {
+ const float factor = (lengths[eval_index - 1] - segment_start_len) * length_factor;
+ mappings[eval_index] = i + factor;
+ }
+ }
+ });
+
+ if (is_cyclic_) {
+ const float segment_start_len = lengths[offsets.last() - 1];
+ const float segment_end_len = this->length();
+ const float segment_len = segment_end_len - segment_start_len;
+ const float length_factor = (segment_len == 0.0f) ? 0.0f : 1.0f / segment_len;
+
+ for (const int eval_index : IndexRange(offsets.last(), eval_size - offsets.last())) {
+ const float factor = (lengths[eval_index - 1] - segment_start_len) * length_factor;
+ mappings[eval_index] = size - 1 + factor;
+ }
+ mappings.last() = 0.0f;
+ }
+ else {
+ mappings.last() = size - 1;
+ }
+
+ mapping_cache_dirty_ = false;
+ return mappings;
+}
+
+Span<float3> BezierSpline::evaluated_positions() const
+{
+ if (!position_cache_dirty_) {
+ return evaluated_position_cache_;
+ }
+
+ std::lock_guard lock{position_cache_mutex_};
+ if (!position_cache_dirty_) {
+ return evaluated_position_cache_;
+ }
+
+ const int eval_size = this->evaluated_points_size();
+ evaluated_position_cache_.resize(eval_size);
+
+ MutableSpan<float3> positions = evaluated_position_cache_;
+
+ Span<int> offsets = this->control_point_offsets();
+ BLI_assert(offsets.last() <= eval_size);
+
+ const int grain_size = std::max(512 / resolution_, 1);
+ blender::parallel_for(IndexRange(this->size() - 1), grain_size, [&](IndexRange range) {
+ for (const int i : range) {
+ this->evaluate_bezier_segment(
+ i, i + 1, positions.slice(offsets[i], offsets[i + 1] - offsets[i]));
+ }
+ });
+
+ const int i_last = this->size() - 1;
+ if (is_cyclic_) {
+ this->evaluate_bezier_segment(i_last, 0, positions.slice(offsets.last(), resolution_));
+ }
+ else {
+ /* Since evualating the bezier segment doesn't add the final point,
+ * it must be added manually in the non-cyclic case. */
+ positions.last() = positions_.last();
+ }
+
+ position_cache_dirty_ = false;
+ return positions;
+}
+
+/**
+ * Convert the data encoded in #evaulated_mappings into its parts-- the information necessary
+ * to interpolate data from control points to evaluated points between them. The next control
+ * point index result will not overflow the size of the vector.
+ */
+BezierSpline::InterpolationData BezierSpline::interpolation_data_from_index_factor(
+ const float index_factor) const
+{
+ const int points_len = this->size();
+ const int index = std::floor(index_factor);
+ if (index == points_len) {
+ BLI_assert(is_cyclic_);
+ return InterpolationData{points_len - 1, 0, 1.0f};
+ }
+ if (index == points_len - 1) {
+ return InterpolationData{points_len - 2, points_len - 1, 1.0f};
+ }
+ return InterpolationData{index, index + 1, index_factor - index};
+}
+
+/* Use a spline argument to avoid adding this to the header. */
+template<typename T>
+static void interpolate_to_evaluated_points_impl(const BezierSpline &spline,
+ const blender::VArray<T> &source_data,
+ MutableSpan<T> result_data)
+{
+ Span<float> mappings = spline.evaluated_mappings();
+
+ for (const int i : result_data.index_range()) {
+ BezierSpline::InterpolationData interp = spline.interpolation_data_from_index_factor(
+ mappings[i]);
+
+ const T &value = source_data[interp.control_point_index];
+ const T &next_value = source_data[interp.next_control_point_index];
+
+ result_data[i] = blender::attribute_math::mix2(interp.factor, value, next_value);
+ }
+}
+
+blender::fn::GVArrayPtr BezierSpline::interpolate_to_evaluated_points(
+ const blender::fn::GVArray &source_data) const
+{
+ BLI_assert(source_data.size() == this->size());
+
+ const int eval_size = this->evaluated_points_size();
+ if (eval_size == 1) {
+ return source_data.shallow_copy();
+ }
+
+ 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<blender::attribute_math::DefaultMixer<T>>) {
+ Array<T> values(eval_size);
+ interpolate_to_evaluated_points_impl<T>(*this, source_data.typed<T>(), values);
+ new_varray = std::make_unique<blender::fn::GVArray_For_ArrayContainer<Array<T>>>(
+ std::move(values));
+ }
+ });
+
+ return new_varray;
+}