diff options
Diffstat (limited to 'source/blender/blenkernel/intern/spline_bezier.cc')
| -rw-r--r-- | source/blender/blenkernel/intern/spline_bezier.cc | 378 |
1 files changed, 378 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..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<BezierSpline>(*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<float3> BezierSpline::positions() +{ + return this->positions_; +} +Span<float3> BezierSpline::positions() const +{ + return this->positions_; +} +MutableSpan<float> BezierSpline::radii() +{ + return this->radii_; +} +Span<float> BezierSpline::radii() const +{ + return this->radii_; +} +MutableSpan<float> BezierSpline::tilts() +{ + return this->tilts_; +} +Span<float> BezierSpline::tilts() const +{ + return this->tilts_; +} +Span<BezierSpline::HandleType> BezierSpline::handle_types_start() const +{ + return this->handle_types_start_; +} +MutableSpan<BezierSpline::HandleType> BezierSpline::handle_types_start() +{ + return this->handle_types_start_; +} +Span<float3> BezierSpline::handle_positions_start() const +{ + return this->handle_positions_start_; +} +MutableSpan<float3> BezierSpline::handle_positions_start() +{ + return this->handle_positions_start_; +} +Span<BezierSpline::HandleType> BezierSpline::handle_types_end() const +{ + return this->handle_types_end_; +} +MutableSpan<BezierSpline::HandleType> BezierSpline::handle_types_end() +{ + return this->handle_types_end_; +} +Span<float3> BezierSpline::handle_positions_end() const +{ + return this->handle_positions_end_; +} +MutableSpan<float3> 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<float3> 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<float3> result) +{ + const float len = static_cast<float>(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<float3> evaluated_positions, + MutableSpan<PointMapping> 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<float3> positions, + MutableSpan<PointMapping> 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<float3> positions, + MutableSpan<PointMapping> 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 |