diff options
Diffstat (limited to 'source/blender/nodes/geometry/nodes/legacy/node_geo_legacy_curve_subdivide.cc')
-rw-r--r-- | source/blender/nodes/geometry/nodes/legacy/node_geo_legacy_curve_subdivide.cc | 393 |
1 files changed, 393 insertions, 0 deletions
diff --git a/source/blender/nodes/geometry/nodes/legacy/node_geo_legacy_curve_subdivide.cc b/source/blender/nodes/geometry/nodes/legacy/node_geo_legacy_curve_subdivide.cc new file mode 100644 index 00000000000..9878402dd35 --- /dev/null +++ b/source/blender/nodes/geometry/nodes/legacy/node_geo_legacy_curve_subdivide.cc @@ -0,0 +1,393 @@ +/* + * 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_task.hh" +#include "BLI_timeit.hh" + +#include "BKE_attribute_math.hh" +#include "BKE_spline.hh" + +#include "UI_interface.h" +#include "UI_resources.h" + +#include "node_geometry_util.hh" + +namespace blender::nodes::node_geo_legacy_curve_subdivide_cc { + +static void node_declare(NodeDeclarationBuilder &b) +{ + b.add_input<decl::Geometry>(N_("Geometry")); + b.add_input<decl::String>(N_("Cuts")); + b.add_input<decl::Int>(N_("Cuts"), "Cuts_001").default_value(1).min(0).max(1000); + b.add_output<decl::Geometry>(N_("Geometry")); +} + +static void node_layout(uiLayout *layout, bContext *UNUSED(C), PointerRNA *ptr) +{ + uiLayoutSetPropSep(layout, true); + uiLayoutSetPropDecorate(layout, false); + uiItemR(layout, ptr, "cuts_type", 0, IFACE_("Cuts"), ICON_NONE); +} + +static void node_init(bNodeTree *UNUSED(tree), bNode *node) +{ + NodeGeometryCurveSubdivide *data = (NodeGeometryCurveSubdivide *)MEM_callocN( + sizeof(NodeGeometryCurveSubdivide), __func__); + + data->cuts_type = GEO_NODE_ATTRIBUTE_INPUT_INTEGER; + node->storage = data; +} + +static void node_update(bNodeTree *ntree, bNode *node) +{ + NodeGeometryPointTranslate &node_storage = *(NodeGeometryPointTranslate *)node->storage; + + update_attribute_input_socket_availabilities( + *ntree, *node, "Cuts", (GeometryNodeAttributeInputMode)node_storage.input_type); +} + +static Array<int> get_subdivided_offsets(const Spline &spline, + const VArray<int> &cuts, + const int spline_offset) +{ + Array<int> offsets(spline.segments_size() + 1); + int offset = 0; + for (const int i : IndexRange(spline.segments_size())) { + offsets[i] = offset; + offset = offset + std::max(cuts[spline_offset + i], 0) + 1; + } + offsets.last() = offset; + return offsets; +} + +template<typename T> +static void subdivide_attribute(Span<T> src, + const Span<int> offsets, + const bool is_cyclic, + MutableSpan<T> dst) +{ + const int src_size = src.size(); + threading::parallel_for(IndexRange(src_size - 1), 1024, [&](IndexRange range) { + for (const int i : range) { + const int cuts = offsets[i + 1] - offsets[i]; + dst[offsets[i]] = src[i]; + const float factor_delta = 1.0f / (cuts + 1.0f); + for (const int cut : IndexRange(cuts)) { + const float factor = (cut + 1) * factor_delta; + dst[offsets[i] + cut] = attribute_math::mix2(factor, src[i], src[i + 1]); + } + } + }); + + if (is_cyclic) { + const int i = src_size - 1; + const int cuts = offsets[i + 1] - offsets[i]; + dst[offsets[i]] = src.last(); + const float factor_delta = 1.0f / (cuts + 1.0f); + for (const int cut : IndexRange(cuts)) { + const float factor = (cut + 1) * factor_delta; + dst[offsets[i] + cut] = attribute_math::mix2(factor, src.last(), src.first()); + } + } + else { + dst.last() = src.last(); + } +} + +/** + * In order to generate a Bezier spline with the same shape as the input spline, apply the + * De Casteljau algorithm iteratively for the provided number of cuts, constantly updating the + * previous result point's right handle and the left handle at the end of the segment. + * + * \note Non-vector segments in the result spline are given free handles. This could possibly be + * improved with another pass that sets handles to aligned where possible, but currently that does + * not provide much benefit for the increased complexity. + */ +static void subdivide_bezier_segment(const BezierSpline &src, + const int index, + const int offset, + const int result_size, + Span<float3> src_positions, + Span<float3> src_handles_left, + Span<float3> src_handles_right, + MutableSpan<float3> dst_positions, + MutableSpan<float3> dst_handles_left, + MutableSpan<float3> dst_handles_right, + MutableSpan<BezierSpline::HandleType> dst_type_left, + MutableSpan<BezierSpline::HandleType> dst_type_right) +{ + const bool is_last_cyclic_segment = index == (src.size() - 1); + const int next_index = is_last_cyclic_segment ? 0 : index + 1; + + /* The first point in the segment is always copied. */ + dst_positions[offset] = src_positions[index]; + + if (src.segment_is_vector(index)) { + if (is_last_cyclic_segment) { + dst_type_left.first() = BezierSpline::HandleType::Vector; + } + dst_type_left.slice(offset + 1, result_size).fill(BezierSpline::HandleType::Vector); + dst_type_right.slice(offset, result_size).fill(BezierSpline::HandleType::Vector); + + const float factor_delta = 1.0f / result_size; + for (const int cut : IndexRange(result_size)) { + const float factor = cut * factor_delta; + dst_positions[offset + cut] = attribute_math::mix2( + factor, src_positions[index], src_positions[next_index]); + } + } + else { + if (is_last_cyclic_segment) { + dst_type_left.first() = BezierSpline::HandleType::Free; + } + dst_type_left.slice(offset + 1, result_size).fill(BezierSpline::HandleType::Free); + dst_type_right.slice(offset, result_size).fill(BezierSpline::HandleType::Free); + + const int i_segment_last = is_last_cyclic_segment ? 0 : offset + result_size; + + /* Create a Bezier segment to update iteratively for every subdivision + * and references to the meaningful values for ease of use. */ + BezierSpline temp; + temp.resize(2); + float3 &segment_start = temp.positions().first(); + float3 &segment_end = temp.positions().last(); + float3 &handle_prev = temp.handle_positions_right().first(); + float3 &handle_next = temp.handle_positions_left().last(); + segment_start = src_positions[index]; + segment_end = src_positions[next_index]; + handle_prev = src_handles_right[index]; + handle_next = src_handles_left[next_index]; + + for (const int cut : IndexRange(result_size - 1)) { + const float parameter = 1.0f / (result_size - cut); + const BezierSpline::InsertResult insert = temp.calculate_segment_insertion(0, 1, parameter); + + /* Copy relevant temporary data to the result. */ + dst_handles_right[offset + cut] = insert.handle_prev; + dst_handles_left[offset + cut + 1] = insert.left_handle; + dst_positions[offset + cut + 1] = insert.position; + + /* Update the segment to prepare it for the next subdivision. */ + segment_start = insert.position; + handle_prev = insert.right_handle; + handle_next = insert.handle_next; + } + + /* Copy the handles for the last segment from the temporary spline. */ + dst_handles_right[offset + result_size - 1] = handle_prev; + dst_handles_left[i_segment_last] = handle_next; + } +} + +static void subdivide_bezier_spline(const BezierSpline &src, + const Span<int> offsets, + BezierSpline &dst) +{ + Span<float3> src_positions = src.positions(); + Span<float3> src_handles_left = src.handle_positions_left(); + Span<float3> src_handles_right = src.handle_positions_right(); + MutableSpan<float3> dst_positions = dst.positions(); + MutableSpan<float3> dst_handles_left = dst.handle_positions_left(); + MutableSpan<float3> dst_handles_right = dst.handle_positions_right(); + MutableSpan<BezierSpline::HandleType> dst_type_left = dst.handle_types_left(); + MutableSpan<BezierSpline::HandleType> dst_type_right = dst.handle_types_right(); + + threading::parallel_for(IndexRange(src.size() - 1), 512, [&](IndexRange range) { + for (const int i : range) { + subdivide_bezier_segment(src, + i, + offsets[i], + offsets[i + 1] - offsets[i], + src_positions, + src_handles_left, + src_handles_right, + dst_positions, + dst_handles_left, + dst_handles_right, + dst_type_left, + dst_type_right); + } + }); + + if (src.is_cyclic()) { + const int i_last = src.size() - 1; + subdivide_bezier_segment(src, + i_last, + offsets[i_last], + offsets.last() - offsets[i_last], + src_positions, + src_handles_left, + src_handles_right, + dst_positions, + dst_handles_left, + dst_handles_right, + dst_type_left, + dst_type_right); + } + else { + dst_positions.last() = src_positions.last(); + } +} + +static void subdivide_builtin_attributes(const Spline &src_spline, + const Span<int> offsets, + Spline &dst_spline) +{ + const bool is_cyclic = src_spline.is_cyclic(); + subdivide_attribute<float>(src_spline.radii(), offsets, is_cyclic, dst_spline.radii()); + subdivide_attribute<float>(src_spline.tilts(), offsets, is_cyclic, dst_spline.tilts()); + switch (src_spline.type()) { + case Spline::Type::Poly: { + const PolySpline &src = static_cast<const PolySpline &>(src_spline); + PolySpline &dst = static_cast<PolySpline &>(dst_spline); + subdivide_attribute<float3>(src.positions(), offsets, is_cyclic, dst.positions()); + break; + } + case Spline::Type::Bezier: { + const BezierSpline &src = static_cast<const BezierSpline &>(src_spline); + BezierSpline &dst = static_cast<BezierSpline &>(dst_spline); + subdivide_bezier_spline(src, offsets, dst); + dst.mark_cache_invalid(); + break; + } + case Spline::Type::NURBS: { + const NURBSpline &src = static_cast<const NURBSpline &>(src_spline); + NURBSpline &dst = static_cast<NURBSpline &>(dst_spline); + subdivide_attribute<float3>(src.positions(), offsets, is_cyclic, dst.positions()); + subdivide_attribute<float>(src.weights(), offsets, is_cyclic, dst.weights()); + break; + } + } +} + +static void subdivide_dynamic_attributes(const Spline &src_spline, + const Span<int> offsets, + Spline &dst_spline) +{ + const bool is_cyclic = src_spline.is_cyclic(); + src_spline.attributes.foreach_attribute( + [&](const bke::AttributeIDRef &attribute_id, const AttributeMetaData &meta_data) { + std::optional<GSpan> src = src_spline.attributes.get_for_read(attribute_id); + BLI_assert(src); + + if (!dst_spline.attributes.create(attribute_id, meta_data.data_type)) { + /* Since the source spline of the same type had the attribute, adding it should work. */ + BLI_assert_unreachable(); + } + + std::optional<GMutableSpan> dst = dst_spline.attributes.get_for_write(attribute_id); + BLI_assert(dst); + + attribute_math::convert_to_static_type(dst->type(), [&](auto dummy) { + using T = decltype(dummy); + subdivide_attribute<T>(src->typed<T>(), offsets, is_cyclic, dst->typed<T>()); + }); + return true; + }, + ATTR_DOMAIN_POINT); +} + +static SplinePtr subdivide_spline(const Spline &spline, + const VArray<int> &cuts, + const int spline_offset) +{ + if (spline.size() <= 1) { + return spline.copy(); + } + + /* Since we expect to access each value many times, it should be worth it to make sure count + * of cuts is a real span (especially considering the note below). Using the offset at each + * point facilitates subdividing in parallel later. */ + Array<int> offsets = get_subdivided_offsets(spline, cuts, spline_offset); + const int result_size = offsets.last() + int(!spline.is_cyclic()); + SplinePtr new_spline = spline.copy_only_settings(); + new_spline->resize(result_size); + subdivide_builtin_attributes(spline, offsets, *new_spline); + subdivide_dynamic_attributes(spline, offsets, *new_spline); + return new_spline; +} + +/** + * \note Passing the virtual array for the entire spline is possibly quite inefficient here when + * the attribute was on the point domain and stored separately for each spline already, and it + * prevents some other optimizations like skipping splines with a single attribute value of < 1. + * However, it allows the node to access builtin attribute easily, so it the makes most sense this + * way until the attribute API is refactored. + */ +static std::unique_ptr<CurveEval> subdivide_curve(const CurveEval &input_curve, + const VArray<int> &cuts) +{ + const Array<int> control_point_offsets = input_curve.control_point_offsets(); + const Span<SplinePtr> input_splines = input_curve.splines(); + + std::unique_ptr<CurveEval> output_curve = std::make_unique<CurveEval>(); + output_curve->resize(input_splines.size()); + output_curve->attributes = input_curve.attributes; + MutableSpan<SplinePtr> output_splines = output_curve->splines(); + + threading::parallel_for(input_splines.index_range(), 128, [&](IndexRange range) { + for (const int i : range) { + output_splines[i] = subdivide_spline(*input_splines[i], cuts, control_point_offsets[i]); + } + }); + + return output_curve; +} + +static void node_geo_exec(GeoNodeExecParams params) +{ + GeometrySet geometry_set = params.extract_input<GeometrySet>("Geometry"); + + geometry_set = geometry::realize_instances_legacy(geometry_set); + + if (!geometry_set.has_curve()) { + params.set_output("Geometry", geometry_set); + return; + } + + const CurveComponent &component = *geometry_set.get_component_for_read<CurveComponent>(); + VArray<int> cuts = params.get_input_attribute<int>("Cuts", component, ATTR_DOMAIN_POINT, 0); + if (cuts.is_single() && cuts.get_internal_single() < 1) { + params.set_output("Geometry", geometry_set); + return; + } + + std::unique_ptr<CurveEval> output_curve = subdivide_curve(*component.get_for_read(), cuts); + + params.set_output("Geometry", GeometrySet::create_with_curve(output_curve.release())); +} + +} // namespace blender::nodes::node_geo_legacy_curve_subdivide_cc + +void register_node_type_geo_legacy_curve_subdivide() +{ + namespace file_ns = blender::nodes::node_geo_legacy_curve_subdivide_cc; + + static bNodeType ntype; + + geo_node_type_base( + &ntype, GEO_NODE_LEGACY_CURVE_SUBDIVIDE, "Curve Subdivide", NODE_CLASS_GEOMETRY, 0); + ntype.declare = file_ns::node_declare; + ntype.draw_buttons = file_ns::node_layout; + node_type_storage(&ntype, + "NodeGeometryCurveSubdivide", + node_free_standard_storage, + node_copy_standard_storage); + node_type_init(&ntype, file_ns::node_init); + node_type_update(&ntype, file_ns::node_update); + ntype.geometry_node_execute = file_ns::node_geo_exec; + nodeRegisterType(&ntype); +} |