From aae96176e8c36c8bcc64e94499975ff3b0b6ec0c Mon Sep 17 00:00:00 2001 From: guitargeek Date: Fri, 1 Oct 2021 09:40:57 -0500 Subject: Geometry Nodes: Curve Subdivide Node with Fields The curve subdivide node can now take an int field to specify the number of subdivisions to make at each curve segment. Reviewed by: Hans Goudey Differential Revision: https://developer.blender.org/D12534 --- source/blender/blenkernel/BKE_node.h | 1 + source/blender/blenkernel/intern/node.cc | 1 + source/blender/makesrna/intern/rna_nodetree.c | 2 +- source/blender/nodes/CMakeLists.txt | 1 + source/blender/nodes/NOD_geometry.h | 1 + source/blender/nodes/NOD_static_types.h | 3 +- .../nodes/legacy/node_geo_curve_subdivide.cc | 2 +- .../geometry/nodes/node_geo_curve_subdivide.cc | 364 +++++++++++++++++++++ 8 files changed, 372 insertions(+), 3 deletions(-) create mode 100644 source/blender/nodes/geometry/nodes/node_geo_curve_subdivide.cc (limited to 'source/blender') diff --git a/source/blender/blenkernel/BKE_node.h b/source/blender/blenkernel/BKE_node.h index a4fc4800fd2..bfce3718f82 100644 --- a/source/blender/blenkernel/BKE_node.h +++ b/source/blender/blenkernel/BKE_node.h @@ -1509,6 +1509,7 @@ int ntreeTexExecTree(struct bNodeTree *ntree, #define GEO_NODE_CURVE_REVERSE 1095 #define GEO_NODE_PROXIMITY 1096 +#define GEO_NODE_CURVE_SUBDIVIDE 1097 /** \} */ /* -------------------------------------------------------------------- */ diff --git a/source/blender/blenkernel/intern/node.cc b/source/blender/blenkernel/intern/node.cc index 66f917ffd96..2df9d2ab32c 100644 --- a/source/blender/blenkernel/intern/node.cc +++ b/source/blender/blenkernel/intern/node.cc @@ -5714,6 +5714,7 @@ static void registerGeometryNodes() register_node_type_geo_legacy_material_assign(); register_node_type_geo_legacy_select_by_material(); register_node_type_geo_legacy_curve_reverse(); + register_node_type_geo_legacy_curve_subdivide(); register_node_type_geo_align_rotation_to_vector(); register_node_type_geo_attribute_capture(); diff --git a/source/blender/makesrna/intern/rna_nodetree.c b/source/blender/makesrna/intern/rna_nodetree.c index 894a8bad6da..ad1331faf2f 100644 --- a/source/blender/makesrna/intern/rna_nodetree.c +++ b/source/blender/makesrna/intern/rna_nodetree.c @@ -10280,7 +10280,7 @@ static void def_geo_curve_resample(StructRNA *srna) RNA_def_property_update(prop, NC_NODE | NA_EDITED, "rna_Node_socket_update"); } -static void def_geo_curve_subdivide(StructRNA *srna) +static void def_geo_legacy_curve_subdivide(StructRNA *srna) { PropertyRNA *prop; diff --git a/source/blender/nodes/CMakeLists.txt b/source/blender/nodes/CMakeLists.txt index 5b6a5ac5b33..7c243e8ce55 100644 --- a/source/blender/nodes/CMakeLists.txt +++ b/source/blender/nodes/CMakeLists.txt @@ -209,6 +209,7 @@ set(SRC geometry/nodes/node_geo_curve_resample.cc geometry/nodes/node_geo_curve_reverse.cc geometry/nodes/node_geo_curve_sample.cc + geometry/nodes/node_geo_curve_subdivide.cc geometry/nodes/node_geo_curve_to_mesh.cc geometry/nodes/node_geo_curve_trim.cc geometry/nodes/node_geo_distribute_points_on_faces.cc diff --git a/source/blender/nodes/NOD_geometry.h b/source/blender/nodes/NOD_geometry.h index af8661d9b8d..d4cde483a12 100644 --- a/source/blender/nodes/NOD_geometry.h +++ b/source/blender/nodes/NOD_geometry.h @@ -34,6 +34,7 @@ void register_node_type_geo_legacy_attribute_randomize(void); void register_node_type_geo_legacy_material_assign(void); void register_node_type_geo_legacy_select_by_material(void); void register_node_type_geo_legacy_curve_reverse(void); +void register_node_type_geo_legacy_curve_subdivide(void); void register_node_type_geo_align_rotation_to_vector(void); void register_node_type_geo_attribute_capture(void); diff --git a/source/blender/nodes/NOD_static_types.h b/source/blender/nodes/NOD_static_types.h index 7972609aa27..a65ff73ab89 100644 --- a/source/blender/nodes/NOD_static_types.h +++ b/source/blender/nodes/NOD_static_types.h @@ -299,7 +299,7 @@ DefNode(GeometryNode, GEO_NODE_LEGACY_CURVE_REVERSE, 0, "LEGACY_CURVE_REVERSE", DefNode(GeometryNode, GEO_NODE_LEGACY_CURVE_SELECT_HANDLES, def_geo_curve_select_handles, "LEGACY_CURVE_SELECT_HANDLES", LegacyCurveSelectHandles, "Select by Handle Type", "") DefNode(GeometryNode, GEO_NODE_LEGACY_CURVE_SET_HANDLES, def_geo_curve_set_handles, "LEGACY_CURVE_SET_HANDLES", LegacyCurveSetHandles, "Set Handle Type", "") DefNode(GeometryNode, GEO_NODE_LEGACY_CURVE_SPLINE_TYPE, def_geo_curve_spline_type, "LEGACY_CURVE_SPLINE_TYPE", LegacyCurveSplineType, "Set Spline Type", "") -DefNode(GeometryNode, GEO_NODE_LEGACY_CURVE_SUBDIVIDE, def_geo_curve_subdivide, "LEGACY_CURVE_SUBDIVIDE", LegacyCurveSubdivide, "Curve Subdivide", "") +DefNode(GeometryNode, GEO_NODE_LEGACY_CURVE_SUBDIVIDE, def_geo_legacy_curve_subdivide, "LEGACY_CURVE_SUBDIVIDE", LegacyCurveSubdivide, "Curve Subdivide", "") DefNode(GeometryNode, GEO_NODE_LEGACY_CURVE_TO_POINTS, def_geo_curve_to_points, "LEGACY_CURVE_TO_POINTS", LegacyCurveToPoints, "Curve to Points", "") DefNode(GeometryNode, GEO_NODE_LEGACY_DELETE_GEOMETRY, 0, "LEGACY_DELETE_GEOMETRY", LegacyDeleteGeometry, "Delete Geometry", "") DefNode(GeometryNode, GEO_NODE_LEGACY_EDGE_SPLIT, 0, "LEGACY_EDGE_SPLIT", LegacyEdgeSplit, "Edge Split", "") @@ -337,6 +337,7 @@ DefNode(GeometryNode, GEO_NODE_CURVE_PRIMITIVE_STAR, 0, "CURVE_PRIMITIVE_STAR", DefNode(GeometryNode, GEO_NODE_CURVE_RESAMPLE, def_geo_curve_resample, "CURVE_RESAMPLE", CurveResample, "Resample Curve", "") DefNode(GeometryNode, GEO_NODE_CURVE_REVERSE, 0, "CURVE_REVERSE", CurveReverse, "Curve Reverse", "") DefNode(GeometryNode, GEO_NODE_CURVE_SAMPLE, def_geo_curve_sample, "CURVE_SAMPLE", CurveSample, "Curve Sample", "") +DefNode(GeometryNode, GEO_NODE_CURVE_SUBDIVIDE, 0, "CURVE_SUBDIVIDE", CurveSubdivide, "Curve Subdivide", "") DefNode(GeometryNode, GEO_NODE_CURVE_TO_MESH, 0, "CURVE_TO_MESH", CurveToMesh, "Curve to Mesh", "") DefNode(GeometryNode, GEO_NODE_CURVE_TRIM, def_geo_curve_trim, "CURVE_TRIM", CurveTrim, "Curve Trim", "") DefNode(GeometryNode, GEO_NODE_DISTRIBUTE_POINTS_ON_FACES, def_geo_distribute_points_on_faces, "DISTRIBUTE_POINTS_ON_FACES", DistributePointsOnFaces, "Distribute Points on Faces", "") diff --git a/source/blender/nodes/geometry/nodes/legacy/node_geo_curve_subdivide.cc b/source/blender/nodes/geometry/nodes/legacy/node_geo_curve_subdivide.cc index 0522f2b8981..f32a68bc042 100644 --- a/source/blender/nodes/geometry/nodes/legacy/node_geo_curve_subdivide.cc +++ b/source/blender/nodes/geometry/nodes/legacy/node_geo_curve_subdivide.cc @@ -373,7 +373,7 @@ static void geo_node_subdivide_exec(GeoNodeExecParams params) } // namespace blender::nodes -void register_node_type_geo_curve_subdivide() +void register_node_type_geo_legacy_curve_subdivide() { static bNodeType ntype; diff --git a/source/blender/nodes/geometry/nodes/node_geo_curve_subdivide.cc b/source/blender/nodes/geometry/nodes/node_geo_curve_subdivide.cc new file mode 100644 index 00000000000..34997c66cbb --- /dev/null +++ b/source/blender/nodes/geometry/nodes/node_geo_curve_subdivide.cc @@ -0,0 +1,364 @@ +/* + * 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" + +using blender::fn::GVArray_For_GSpan; +using blender::fn::GVArray_For_Span; +using blender::fn::GVArray_Typed; + +namespace blender::nodes { + +static void geo_node_curve_subdivide_declare(NodeDeclarationBuilder &b) +{ + b.add_input("Geometry"); + b.add_input("Cuts").default_value(1).min(0).max(1000).supports_field(); + b.add_output("Geometry"); +} + +static Array get_subdivided_offsets(const Spline &spline, + const VArray &cuts, + const int spline_offset) +{ + Array 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 +static void subdivide_attribute(Span src, + const Span offsets, + const bool is_cyclic, + MutableSpan 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 src_positions, + Span src_handles_left, + Span src_handles_right, + MutableSpan dst_positions, + MutableSpan dst_handles_left, + MutableSpan dst_handles_right, + MutableSpan dst_type_left, + MutableSpan 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 offsets, + BezierSpline &dst) +{ + Span src_positions = src.positions(); + Span src_handles_left = src.handle_positions_left(); + Span src_handles_right = src.handle_positions_right(); + MutableSpan dst_positions = dst.positions(); + MutableSpan dst_handles_left = dst.handle_positions_left(); + MutableSpan dst_handles_right = dst.handle_positions_right(); + MutableSpan dst_type_left = dst.handle_types_left(); + MutableSpan 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 offsets, + Spline &dst_spline) +{ + const bool is_cyclic = src_spline.is_cyclic(); + subdivide_attribute(src_spline.radii(), offsets, is_cyclic, dst_spline.radii()); + subdivide_attribute(src_spline.tilts(), offsets, is_cyclic, dst_spline.tilts()); + switch (src_spline.type()) { + case Spline::Type::Poly: { + const PolySpline &src = static_cast(src_spline); + PolySpline &dst = static_cast(dst_spline); + subdivide_attribute(src.positions(), offsets, is_cyclic, dst.positions()); + break; + } + case Spline::Type::Bezier: { + const BezierSpline &src = static_cast(src_spline); + BezierSpline &dst = static_cast(dst_spline); + subdivide_bezier_spline(src, offsets, dst); + dst.mark_cache_invalid(); + break; + } + case Spline::Type::NURBS: { + const NURBSpline &src = static_cast(src_spline); + NURBSpline &dst = static_cast(dst_spline); + subdivide_attribute(src.positions(), offsets, is_cyclic, dst.positions()); + subdivide_attribute(src.weights(), offsets, is_cyclic, dst.weights()); + break; + } + } +} + +static void subdivide_dynamic_attributes(const Spline &src_spline, + const Span 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 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 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(src->typed(), offsets, is_cyclic, dst->typed()); + }); + return true; + }, + ATTR_DOMAIN_POINT); +} + +static SplinePtr subdivide_spline(const Spline &spline, + const VArray &cuts, + const int spline_offset) +{ + /* Since we expect to access each value many times, it should be worth it to make sure the + * attribute is a real span (especially considering the note below). Using the offset at each + * point facilitates subdividing in parallel later. */ + Array 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 subdivide_curve(const CurveEval &input_curve, + const VArray &cuts) +{ + const Array control_point_offsets = input_curve.control_point_offsets(); + const Span input_splines = input_curve.splines(); + + std::unique_ptr output_curve = std::make_unique(); + output_curve->resize(input_splines.size()); + output_curve->attributes = input_curve.attributes; + MutableSpan 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 geo_node_subdivide_exec(GeoNodeExecParams params) +{ + GeometrySet geometry_set = params.extract_input("Geometry"); + Field cuts_field = params.extract_input>("Cuts"); + + geometry_set.modify_geometry_sets([&](GeometrySet &geometry_set) { + if (!geometry_set.has_curve()) { + return; + } + + const CurveComponent &component = *geometry_set.get_component_for_read(); + GeometryComponentFieldContext field_context{component, ATTR_DOMAIN_POINT}; + const int domain_size = component.attribute_domain_size(ATTR_DOMAIN_POINT); + + fn::FieldEvaluator evaluator{field_context, domain_size}; + evaluator.add(cuts_field); + evaluator.evaluate(); + const VArray &cuts = evaluator.get_evaluated(0); + + if (cuts.is_single() && cuts.get_internal_single() < 1) { + return; + } + + std::unique_ptr output_curve = subdivide_curve(*component.get_for_read(), cuts); + geometry_set.replace_curve(output_curve.release()); + }); + params.set_output("Geometry", geometry_set); +} + +} // namespace blender::nodes + +void register_node_type_geo_curve_subdivide() +{ + static bNodeType ntype; + + geo_node_type_base(&ntype, GEO_NODE_CURVE_SUBDIVIDE, "Curve Subdivide", NODE_CLASS_GEOMETRY, 0); + ntype.declare = blender::nodes::geo_node_curve_subdivide_declare; + ntype.geometry_node_execute = blender::nodes::geo_node_subdivide_exec; + nodeRegisterType(&ntype); +} -- cgit v1.2.3