From 1892b131edc76abb4439ca6fcc69b95a208ab7d7 Mon Sep 17 00:00:00 2001 From: Hans Goudey Date: Wed, 12 May 2021 10:21:12 -0500 Subject: Geometry Nodes Curves: Expose first builtin point attributes This commit exposes the first spline control point attributes. The implementation incorporates the attributes into the virtual array system, providing efficient methods to flatten the data into a contiguous array and to apply changes from a flattened array. This is only part of the eventual goal, which includes changes to run attribute nodes separately for each spline to completely avoid copying. So far `tilt` and `radius`, the two generic attributes common to all spline types, are implemented. The more complex `position` attribute is also added. It requires some special handling for Bezier splines, where the control point handles need to be moved along with the control points. To make that work I also added automatic handle recalculation to the Bezier spline. Differential Revision: https://developer.blender.org/D11187 --- source/blender/blenkernel/BKE_spline.hh | 9 +- .../blenkernel/intern/geometry_component_curve.cc | 427 ++++++++++++++++++++- source/blender/blenkernel/intern/spline_bezier.cc | 82 ++++ 3 files changed, 515 insertions(+), 3 deletions(-) (limited to 'source/blender/blenkernel') diff --git a/source/blender/blenkernel/BKE_spline.hh b/source/blender/blenkernel/BKE_spline.hh index 48b5dfb1623..35bbc23b21a 100644 --- a/source/blender/blenkernel/BKE_spline.hh +++ b/source/blender/blenkernel/BKE_spline.hh @@ -206,8 +206,12 @@ class BezierSpline final : public Spline { blender::Vector handle_types_left_; blender::Vector handle_types_right_; - blender::Vector handle_positions_left_; - blender::Vector handle_positions_right_; + /* These are mutable to allow lazy recalculation of #Auto and #Vector handle positions. */ + mutable blender::Vector handle_positions_left_; + mutable blender::Vector handle_positions_right_; + + mutable std::mutex auto_handle_mutex_; + mutable bool auto_handles_dirty_ = true; /** Start index in evaluated points array for every control point. */ mutable blender::Vector offset_cache_; @@ -296,6 +300,7 @@ class BezierSpline final : public Spline { const blender::fn::GVArray &source_data) const override; private: + void ensure_auto_handles() const; void correct_end_tangents() const final; bool segment_is_vector(const int start_index) const; void evaluate_bezier_segment(const int index, diff --git a/source/blender/blenkernel/intern/geometry_component_curve.cc b/source/blender/blenkernel/intern/geometry_component_curve.cc index 7afecb66bcc..216f0930cf9 100644 --- a/source/blender/blenkernel/intern/geometry_component_curve.cc +++ b/source/blender/blenkernel/intern/geometry_component_curve.cc @@ -285,6 +285,415 @@ static GVMutableArrayPtr make_cyclic_write_attribute(CurveEval &curve) /** \} */ +/* -------------------------------------------------------------------- */ +/** \name Builtin Control Point Attributes + * + * Attributes with a value for every control point. Most of the complexity here is due to the fact + * that we must provide access to the attribute data as if it was a contiguous array when it is + * really stored separately on each spline. That will be inherently rather slow, but these virtual + * array implementations try to make it workable in common situations. + * \{ */ + +static Array control_point_offsets(const CurveEval &curve) +{ + Array offsets(curve.splines.size() + 1); + + int size = 0; + for (const int spline_index : curve.splines.index_range()) { + offsets[spline_index] = size; + size += curve.splines[spline_index]->size(); + } + offsets.last() = size; + + return offsets; +} + +namespace { +struct PointIndices { + int spline_index; + int point_index; +}; +} // namespace +static PointIndices lookup_point_indices(Span offsets, const int index) +{ + const int spline_index = std::upper_bound(offsets.begin(), offsets.end(), index) - + offsets.begin() - 1; + const int index_in_spline = index - offsets[spline_index]; + return {spline_index, index_in_spline}; +} + +template +static void point_attribute_materialize(Span> data, + Span offsets, + const IndexMask mask, + MutableSpan r_span) +{ + const int total_size = offsets.last(); + if (mask.is_range() && mask.as_range() == IndexRange(total_size)) { + for (const int spline_index : data.index_range()) { + const int offset = offsets[spline_index]; + const int next_offset = offsets[spline_index + 1]; + initialized_copy_n(data[spline_index].data(), next_offset - offset, r_span.data() + offset); + } + } + else { + int spline_index = 0; + for (const int i : r_span.index_range()) { + const int dst_index = mask[i]; + + while (offsets[spline_index] < dst_index) { + spline_index++; + } + + const int index_in_spline = dst_index - offsets[spline_index]; + r_span[dst_index] = data[spline_index][index_in_spline]; + } + } +} + +template +static void point_attribute_materialize_to_uninitialized(Span> data, + Span offsets, + const IndexMask mask, + MutableSpan r_span) +{ + T *dst = r_span.data(); + const int total_size = offsets.last(); + if (mask.is_range() && mask.as_range() == IndexRange(total_size)) { + for (const int spline_index : data.index_range()) { + const int offset = offsets[spline_index]; + const int next_offset = offsets[spline_index + 1]; + uninitialized_copy_n(data[spline_index].data(), next_offset - offset, dst + offset); + } + } + else { + int spline_index = 0; + for (const int i : r_span.index_range()) { + const int dst_index = mask[i]; + + while (offsets[spline_index] < dst_index) { + spline_index++; + } + + const int index_in_spline = dst_index - offsets[spline_index]; + new (dst + dst_index) T(data[spline_index][index_in_spline]); + } + } +} + +/** + * Virtual array for any control point data accessed with spans and an offset array. + */ +template class VArray_For_SplinePoints : public VArray { + private: + const Array> data_; + Array offsets_; + + public: + VArray_For_SplinePoints(Array> data, Array offsets) + : VArray(offsets.last()), data_(std::move(data)), offsets_(std::move(offsets)) + { + } + + T get_impl(const int64_t index) const final + { + const PointIndices indices = lookup_point_indices(offsets_, index); + return data_[indices.spline_index][indices.point_index]; + } + + void materialize_impl(const IndexMask mask, MutableSpan r_span) const final + { + point_attribute_materialize(data_.as_span(), offsets_, mask, r_span); + } + + void materialize_to_uninitialized_impl(const IndexMask mask, MutableSpan r_span) const final + { + point_attribute_materialize_to_uninitialized(data_.as_span(), offsets_, mask, r_span); + } +}; + +/** + * Mutable virtual array for any control point data accessed with spans and an offset array. + */ +template class VMutableArray_For_SplinePoints final : public VMutableArray { + private: + Array> data_; + Array offsets_; + + public: + VMutableArray_For_SplinePoints(Array> data, Array offsets) + : VMutableArray(offsets.last()), data_(std::move(data)), offsets_(std::move(offsets)) + { + } + + T get_impl(const int64_t index) const final + { + const PointIndices indices = lookup_point_indices(offsets_, index); + return data_[indices.spline_index][indices.point_index]; + } + + void set_impl(const int64_t index, T value) final + { + const PointIndices indices = lookup_point_indices(offsets_, index); + data_[indices.spline_index][indices.point_index] = value; + } + + void set_all_impl(Span src) final + { + for (const int spline_index : data_.index_range()) { + const int offset = offsets_[spline_index]; + const int next_offsets = offsets_[spline_index + 1]; + data_[spline_index].copy_from(src.slice(offset, next_offsets - offset)); + } + } + + void materialize_impl(const IndexMask mask, MutableSpan r_span) const final + { + point_attribute_materialize({(Span *)data_.data(), data_.size()}, offsets_, mask, r_span); + } + + void materialize_to_uninitialized_impl(const IndexMask mask, MutableSpan r_span) const final + { + point_attribute_materialize_to_uninitialized( + {(Span *)data_.data(), data_.size()}, offsets_, mask, r_span); + } +}; + +/** + * Virtual array implementation specifically for control point positions. This is only needed for + * Bezier splines, where adjusting the position also needs to adjust handle positions depending on + * the handle types. We pay a small price for this when other spline types are mixed with Bezier. + * + * \note There is no need to check the handle type to avoid changing auto handles, since + * retrieving write access to the position data will mark them for recomputation anyway. + */ +class VMutableArray_For_SplinePosition final : public VMutableArray { + private: + MutableSpan splines_; + Array offsets_; + + public: + VMutableArray_For_SplinePosition(MutableSpan splines, Array offsets) + : VMutableArray(offsets.last()), splines_(splines), offsets_(std::move(offsets)) + { + } + + float3 get_impl(const int64_t index) const final + { + const PointIndices indices = lookup_point_indices(offsets_, index); + return splines_[indices.spline_index]->positions()[indices.point_index]; + } + + void set_impl(const int64_t index, float3 value) final + { + const PointIndices indices = lookup_point_indices(offsets_, index); + Spline &spline = *splines_[indices.spline_index]; + if (BezierSpline *bezier_spline = dynamic_cast(&spline)) { + const float3 delta = value - bezier_spline->positions()[indices.point_index]; + bezier_spline->handle_positions_left()[indices.point_index] += delta; + bezier_spline->handle_positions_right()[indices.point_index] += delta; + bezier_spline->positions()[indices.point_index] = value; + } + else { + spline.positions()[indices.point_index] = value; + } + } + + void set_all_impl(Span src) final + { + for (const int spline_index : splines_.index_range()) { + Spline &spline = *splines_[spline_index]; + const int offset = offsets_[spline_index]; + const int next_offset = offsets_[spline_index + 1]; + if (BezierSpline *bezier_spline = dynamic_cast(&spline)) { + MutableSpan positions = bezier_spline->positions(); + MutableSpan handle_positions_left = bezier_spline->handle_positions_left(); + MutableSpan handle_positions_right = bezier_spline->handle_positions_right(); + for (const int i : IndexRange(next_offset - offset)) { + const float3 delta = src[offset + i] - positions[i]; + handle_positions_left[i] += delta; + handle_positions_right[i] += delta; + positions[i] = src[offset + i]; + } + } + else { + spline.positions().copy_from(src.slice(offset, next_offset - offset)); + } + } + } + + /** Utility so we can pass positions to the materialize functions above. */ + Array> get_position_spans() const + { + Array> spans(splines_.size()); + for (const int i : spans.index_range()) { + spans[i] = splines_[i]->positions(); + } + return spans; + } + + void materialize_impl(const IndexMask mask, MutableSpan r_span) const final + { + Array> spans = this->get_position_spans(); + point_attribute_materialize(spans.as_span(), offsets_, mask, r_span); + } + + void materialize_to_uninitialized_impl(const IndexMask mask, + MutableSpan r_span) const final + { + Array> spans = this->get_position_spans(); + point_attribute_materialize_to_uninitialized(spans.as_span(), offsets_, mask, r_span); + } +}; + +/** + * Provider for any builtin control point attribute that doesn't need + * special handling such as access to other arrays in the spline. + */ +template class BuiltinPointAttributeProvider : public BuiltinAttributeProvider { + protected: + using GetSpan = Span (*)(const Spline &spline); + using GetMutableSpan = MutableSpan (*)(Spline &spline); + using UpdateOnWrite = void (*)(Spline &spline); + const GetSpan get_span_; + const GetMutableSpan get_mutable_span_; + const UpdateOnWrite update_on_write_; + + public: + BuiltinPointAttributeProvider(std::string attribute_name, + const WritableEnum writable, + const GetSpan get_span, + const GetMutableSpan get_mutable_span, + const UpdateOnWrite update_on_write) + : BuiltinAttributeProvider(std::move(attribute_name), + ATTR_DOMAIN_POINT, + bke::cpp_type_to_custom_data_type(CPPType::get()), + BuiltinAttributeProvider::NonCreatable, + writable, + BuiltinAttributeProvider::NonDeletable), + get_span_(get_span), + get_mutable_span_(get_mutable_span), + update_on_write_(update_on_write) + { + } + + GVArrayPtr try_get_for_read(const GeometryComponent &component) const + { + const CurveEval *curve = get_curve_from_component_for_read(component); + if (curve == nullptr) { + return {}; + } + + if (curve->splines.size() == 1) { + return std::make_unique(get_span_(*curve->splines.first())); + } + + Array offsets = control_point_offsets(*curve); + Array> spans(curve->splines.size()); + for (const int i : curve->splines.index_range()) { + spans[i] = get_span_(*curve->splines[i]); + } + + return std::make_unique>>( + offsets.last(), std::move(spans), std::move(offsets)); + } + + GVMutableArrayPtr try_get_for_write(GeometryComponent &component) const + { + CurveEval *curve = get_curve_from_component_for_write(component); + if (curve == nullptr) { + return {}; + } + + if (curve->splines.size() == 1) { + return std::make_unique( + get_mutable_span_(*curve->splines.first())); + } + + Array offsets = control_point_offsets(*curve); + Array> spans(curve->splines.size()); + for (const int i : curve->splines.index_range()) { + spans[i] = get_mutable_span_(*curve->splines[i]); + if (update_on_write_) { + update_on_write_(*curve->splines[i]); + } + } + + return std::make_unique< + fn::GVMutableArray_For_EmbeddedVMutableArray>>( + offsets.last(), std::move(spans), std::move(offsets)); + } + + bool try_delete(GeometryComponent &UNUSED(component)) const final + { + return false; + } + + bool try_create(GeometryComponent &UNUSED(component), + const AttributeInit &UNUSED(initializer)) const final + { + return false; + } + + bool exists(const GeometryComponent &component) const final + { + return component.attribute_domain_size(ATTR_DOMAIN_POINT) != 0; + } +}; + +/** + * Special attribute provider for the position attribute. Having this separate means we don't + * need to make #BuiltinPointAttributeProvider overly generic, and the special handling for the + * positions is more clear. + */ +class PositionAttributeProvider final : public BuiltinPointAttributeProvider { + public: + PositionAttributeProvider() + : BuiltinPointAttributeProvider( + "position", + BuiltinAttributeProvider::Writable, + [](const Spline &spline) { return spline.positions(); }, + [](Spline &spline) { return spline.positions(); }, + [](Spline &spline) { spline.mark_cache_invalid(); }) + { + } + + GVMutableArrayPtr try_get_for_write(GeometryComponent &component) const final + { + CurveEval *curve = get_curve_from_component_for_write(component); + if (curve == nullptr) { + return {}; + } + + /* Changing the positions requires recalculation of cached evaluated data in many cases. + * This could set more specific flags in the future to avoid unnecessary recomputation. */ + bool curve_has_bezier_spline = false; + for (SplinePtr &spline : curve->splines) { + if (spline->type() == Spline::Type::Bezier) { + curve_has_bezier_spline = true; + break; + } + } + + /* Use the regular position virtual array there are any bezier splines to potentially avoid + * using the special position virtual array when there are no Bezier splines anyway. */ + if (!curve_has_bezier_spline) { + return BuiltinPointAttributeProvider::try_get_for_write(component); + } + + for (SplinePtr &spline : curve->splines) { + spline->mark_cache_invalid(); + } + + Array offsets = control_point_offsets(*curve); + return std::make_unique< + fn::GVMutableArray_For_EmbeddedVMutableArray>( + offsets.last(), curve->splines, std::move(offsets)); + } +}; + +/** \} */ + /* -------------------------------------------------------------------- */ /** \name Attribute Provider Declaration * \{ */ @@ -307,7 +716,23 @@ static ComponentAttributeProviders create_attribute_providers_for_curve() make_cyclic_read_attribute, make_cyclic_write_attribute); - return ComponentAttributeProviders({&resolution, &cyclic}, {}); + static PositionAttributeProvider position; + + static BuiltinPointAttributeProvider radius( + "radius", + BuiltinAttributeProvider::Writable, + [](const Spline &spline) { return spline.radii(); }, + [](Spline &spline) { return spline.radii(); }, + nullptr); + + static BuiltinPointAttributeProvider tilt( + "tilt", + BuiltinAttributeProvider::Writable, + [](const Spline &spline) { return spline.tilts(); }, + [](Spline &spline) { return spline.tilts(); }, + [](Spline &spline) { spline.mark_cache_invalid(); }); + + return ComponentAttributeProviders({&position, &radius, &tilt, &resolution, &cyclic}, {}); } } // namespace blender::bke diff --git a/source/blender/blenkernel/intern/spline_bezier.cc b/source/blender/blenkernel/intern/spline_bezier.cc index 20226dc3ed2..0bc6e71fa4d 100644 --- a/source/blender/blenkernel/intern/spline_bezier.cc +++ b/source/blender/blenkernel/intern/spline_bezier.cc @@ -119,10 +119,12 @@ MutableSpan BezierSpline::handle_types_left() } Span BezierSpline::handle_positions_left() const { + this->ensure_auto_handles(); return handle_positions_left_; } MutableSpan BezierSpline::handle_positions_left() { + this->ensure_auto_handles(); return handle_positions_left_; } Span BezierSpline::handle_types_right() const @@ -135,13 +137,90 @@ MutableSpan BezierSpline::handle_types_right() } Span BezierSpline::handle_positions_right() const { + this->ensure_auto_handles(); return handle_positions_right_; } MutableSpan BezierSpline::handle_positions_right() { + this->ensure_auto_handles(); return handle_positions_right_; } +static float3 previous_position(Span positions, const bool cyclic, const int i) +{ + if (i == 0) { + if (cyclic) { + return positions[positions.size() - 1]; + } + return 2.0f * positions[i] - positions[i + 1]; + } + return positions[i - 1]; +} + +static float3 next_position(Span positions, const bool cyclic, const int i) +{ + if (i == positions.size() - 1) { + if (cyclic) { + return positions[0]; + } + return 2.0f * positions[i] - positions[i - 1]; + } + return positions[i + 1]; +} + +void BezierSpline::ensure_auto_handles() const +{ + if (!auto_handles_dirty_) { + return; + } + + std::lock_guard lock{auto_handle_mutex_}; + if (!auto_handles_dirty_) { + return; + } + + for (const int i : IndexRange(this->size())) { + if (ELEM(HandleType::Auto, handle_types_left_[i], handle_types_right_[i])) { + const float3 prev_diff = positions_[i] - previous_position(positions_, is_cyclic_, i); + const float3 next_diff = next_position(positions_, is_cyclic_, i) - positions_[i]; + float prev_len = prev_diff.length(); + float next_len = next_diff.length(); + if (prev_len == 0.0f) { + prev_len = 1.0f; + } + if (next_len == 0.0f) { + next_len = 1.0f; + } + const float3 dir = next_diff / next_len + prev_diff / prev_len; + + /* This magic number is unfortunate, but comes from elsewhere in Blender. */ + const float len = dir.length() * 2.5614f; + if (len != 0.0f) { + if (handle_types_left_[i] == HandleType::Auto) { + const float prev_len_clamped = std::min(prev_len, next_len * 5.0f); + handle_positions_left_[i] = positions_[i] + dir * -(prev_len_clamped / len); + } + if (handle_types_right_[i] == HandleType::Auto) { + const float next_len_clamped = std::min(next_len, prev_len * 5.0f); + handle_positions_right_[i] = positions_[i] + dir * (next_len_clamped / len); + } + } + } + + if (handle_types_left_[i] == HandleType::Vector) { + const float3 prev = previous_position(positions_, is_cyclic_, i); + handle_positions_left_[i] = float3::interpolate(positions_[i], prev, 1.0f / 3.0f); + } + + if (handle_types_right_[i] == HandleType::Vector) { + const float3 next = next_position(positions_, is_cyclic_, i); + handle_positions_right_[i] = float3::interpolate(positions_[i], next, 1.0f / 3.0f); + } + } + + auto_handles_dirty_ = false; +} + void BezierSpline::translate(const blender::float3 &translation) { for (float3 &position : this->positions()) { @@ -195,6 +274,7 @@ void BezierSpline::mark_cache_invalid() tangent_cache_dirty_ = true; normal_cache_dirty_ = true; length_cache_dirty_ = true; + auto_handles_dirty_ = true; } int BezierSpline::evaluated_points_size() const @@ -389,6 +469,8 @@ Span BezierSpline::evaluated_positions() const return evaluated_position_cache_; } + this->ensure_auto_handles(); + const int eval_size = this->evaluated_points_size(); evaluated_position_cache_.resize(eval_size); -- cgit v1.2.3