diff --git a/release/scripts/startup/nodeitems_builtins.py b/release/scripts/startup/nodeitems_builtins.py index b7d09215676..01163dc9ce0 100644 --- a/release/scripts/startup/nodeitems_builtins.py +++ b/release/scripts/startup/nodeitems_builtins.py @@ -649,6 +649,7 @@ geometry_node_categories = [ NodeItem("GeometryNodeAttributeStatistic"), NodeItem("GeometryNodeAttributeTransfer"), NodeItem("GeometryNodeRemoveAttribute"), + NodeItem("GeometryNodeSmoothAttribute"), NodeItem("GeometryNodeStoreNamedAttribute"), ]), GeometryNodeCategory("GEO_COLOR", "Color", items=[ diff --git a/source/blender/blenkernel/BKE_node.h b/source/blender/blenkernel/BKE_node.h index 55bf24f943e..c40c6ae5547 100644 --- a/source/blender/blenkernel/BKE_node.h +++ b/source/blender/blenkernel/BKE_node.h @@ -1525,6 +1525,7 @@ struct TexResult; #define GEO_NODE_INPUT_SHORTEST_EDGE_PATHS 1168 #define GEO_NODE_EDGE_PATHS_TO_CURVES 1169 #define GEO_NODE_EDGE_PATHS_TO_SELECTION 1170 +#define GEO_NODE_SMOOTH_ATTRIBUTE 1171 /** \} */ diff --git a/source/blender/blenkernel/intern/curves_geometry.cc b/source/blender/blenkernel/intern/curves_geometry.cc index 06789e34ad4..8753d0ee6af 100644 --- a/source/blender/blenkernel/intern/curves_geometry.cc +++ b/source/blender/blenkernel/intern/curves_geometry.cc @@ -15,6 +15,9 @@ #include "BLI_math_rotation.hh" #include "BLI_task.hh" + +#include "BLI_packing_task.hh" + #include "DNA_curves_types.h" #include "BKE_attribute_math.hh" @@ -1466,7 +1469,25 @@ static void adapt_curve_domain_point_to_curve_impl(const CurvesGeometry &curves, MutableSpan r_values) { attribute_math::DefaultMixer mixer(r_values); - + + Array curves_points_num(curves.curves_num()); + + for (const int index : curves.curves_range()){ + curves_points_num[index] = curves.points_num_for_curve(index); + } + + packing_task::pack(curves_points_num, 1000, [&](const Span indices){ + Span mixer_mask; + for (const int i_curve : indices){ + for (const int i_point : curves.points_for_curve(i_curve)) { + mixer.mix_in(i_curve, old_values[i_point]); + } + const int64_t fff = i_curve; + mixer_mask = Span(&fff, 1); + mixer.finalize(mixer_mask); + } + }); +/* threading::parallel_for(curves.curves_range(), 128, [&](const IndexRange range) { for (const int i_curve : range) { for (const int i_point : curves.points_for_curve(i_curve)) { @@ -1474,7 +1495,7 @@ static void adapt_curve_domain_point_to_curve_impl(const CurvesGeometry &curves, } } mixer.finalize(range); - }); + });*/ } /** diff --git a/source/blender/blenkernel/intern/node.cc b/source/blender/blenkernel/intern/node.cc index b82cf30416a..6f92128b163 100644 --- a/source/blender/blenkernel/intern/node.cc +++ b/source/blender/blenkernel/intern/node.cc @@ -4784,6 +4784,7 @@ static void registerGeometryNodes() register_node_type_geo_set_shade_smooth(); register_node_type_geo_set_spline_cyclic(); register_node_type_geo_set_spline_resolution(); + register_node_type_geo_smooth_attribute(); register_node_type_geo_store_named_attribute(); register_node_type_geo_string_join(); register_node_type_geo_string_to_curves(); diff --git a/source/blender/blenlib/BLI_packing_task.hh b/source/blender/blenlib/BLI_packing_task.hh new file mode 100644 index 00000000000..c78a1850bab --- /dev/null +++ b/source/blender/blenlib/BLI_packing_task.hh @@ -0,0 +1,56 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ + +#pragma once + +/** \file + */ + +#include "BLI_array.hh" +#include "BLI_vector.hh" +#include "BLI_span.hh" +#include "BLI_sort.hh" +#include "BLI_index_range.hh" +#include "BLI_task.hh" + +namespace blender::packing_task{ + +template +static void pack(const Span weight, const int weight_grain, Function func){ + + Array indices = weight.index_range().as_span(); + parallel_sort(indices.begin(), indices.end(), [&](const int a, const int b){ + return weight[a] < weight[b]; + }); + + int accumulate = 0; + int start = 0; + int end = 0; + + Vector> calls; + calls.reserve(weight.size()); + + auto call = [&](){ + IndexRange range = IndexRange(start, end - start); + Span index_range = indices.as_span().slice(range); + calls.append(index_range); + accumulate = 0; + }; + for (const int index : indices.index_range()){ + const int range_index = index+1; + accumulate += weight[indices[index]]; + if (accumulate >= weight_grain){ + start = end; + end = range_index; + call(); + } + } + if (accumulate != 0) { + start = end; + end = weight.size(); + call(); + } + + threading::parallel_for_each(calls, func); +} + +} // namespace blender::packing_task diff --git a/source/blender/blenlib/BLI_task.hh b/source/blender/blenlib/BLI_task.hh index 33a781d3749..25d83f156fc 100644 --- a/source/blender/blenlib/BLI_task.hh +++ b/source/blender/blenlib/BLI_task.hh @@ -131,4 +131,27 @@ template void isolate_task(const Function &function) #endif } +/* + * The task granulation size must be a power of two. + * If the complexity is dynamic, the calculation may require a fast conversion to a power of two. + */ +inline int prepair_grain_size(const int crude_grain) { +#ifdef WITH_TBB + if (crude_grain <= 0) { + return 1; + } + int power = 0; + int grain = crude_grain; + while (grain != 1) { + grain >>= 1; + power++; + } + const int grain_size = 1 << power; + return grain_size != crude_grain ? grain_size << 1 : grain_size; +#else + /* Any processing of excess. If another addiction appears, the preparation for it should be individual. */ + return crude_grain; +#endif +} + } // namespace blender::threading diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index 470ffebcad4..b6dbfdcfbf9 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -282,6 +282,7 @@ set(SRC BLI_multi_value_map.hh BLI_noise.h BLI_noise.hh + BLI_packing_task.hh BLI_parameter_pack_utils.hh BLI_path_util.h BLI_polyfill_2d.h diff --git a/source/blender/makesrna/intern/rna_nodetree.c b/source/blender/makesrna/intern/rna_nodetree.c index caeee35a80a..793039f0871 100644 --- a/source/blender/makesrna/intern/rna_nodetree.c +++ b/source/blender/makesrna/intern/rna_nodetree.c @@ -9555,6 +9555,20 @@ static void def_geo_accumulate_field(StructRNA *srna) RNA_def_property_update(prop, NC_NODE | NA_EDITED, "rna_Node_update"); } +static void def_geo_smooth_attribute(StructRNA *srna) +{ + PropertyRNA *prop; + + prop = RNA_def_property(srna, "data_type", PROP_ENUM, PROP_NONE); + RNA_def_property_enum_sdna(prop, NULL, "custom1"); + RNA_def_property_enum_items(prop, rna_enum_attribute_type_items); + RNA_def_property_enum_funcs( + prop, NULL, NULL, "rna_GeometryNodeAttributeType_type_with_socket_itemf"); + RNA_def_property_enum_default(prop, CD_PROP_FLOAT); + RNA_def_property_ui_text(prop, "Data Type", ""); + RNA_def_property_update(prop, NC_NODE | NA_EDITED, "rna_GeometryNode_socket_update"); +} + static void def_fn_random_value(StructRNA *srna) { PropertyRNA *prop; diff --git a/source/blender/nodes/NOD_geometry.h b/source/blender/nodes/NOD_geometry.h index e16cd7a253f..3701694b14a 100644 --- a/source/blender/nodes/NOD_geometry.h +++ b/source/blender/nodes/NOD_geometry.h @@ -132,6 +132,7 @@ void register_node_type_geo_set_position(void); void register_node_type_geo_set_shade_smooth(void); void register_node_type_geo_set_spline_cyclic(void); void register_node_type_geo_set_spline_resolution(void); +void register_node_type_geo_smooth_attribute(void); void register_node_type_geo_store_named_attribute(void); void register_node_type_geo_string_join(void); void register_node_type_geo_string_to_curves(void); diff --git a/source/blender/nodes/NOD_static_types.h b/source/blender/nodes/NOD_static_types.h index d587da823f1..151ef41669d 100644 --- a/source/blender/nodes/NOD_static_types.h +++ b/source/blender/nodes/NOD_static_types.h @@ -283,6 +283,7 @@ DefNode(FunctionNode, FN_NODE_VALUE_TO_STRING, 0, "VALUE_TO_STRING", ValueToStri DefNode(GeometryNode, GEO_NODE_ACCUMULATE_FIELD, def_geo_accumulate_field, "ACCUMULATE_FIELD", AccumulateField, "Accumulate Field", "Add the values of an evaluated field together and output the running total for each element") DefNode(GeometryNode, GEO_NODE_ATTRIBUTE_DOMAIN_SIZE, def_geo_attribute_domain_size, "ATTRIBUTE_DOMAIN_SIZE", AttributeDomainSize, "Domain Size", "Retrieve the number of elements in a geometry for each attribute domain") DefNode(GeometryNode, GEO_NODE_ATTRIBUTE_STATISTIC, def_geo_attribute_statistic, "ATTRIBUTE_STATISTIC",AttributeStatistic, "Attribute Statistic","Calculate statistics about a data set from a field evaluated on a geometry") +DefNode(GeometryNode, GEO_NODE_SMOOTH_ATTRIBUTE, def_geo_smooth_attribute, "SMOOTH_ATTRIBUTE", SmoothAttribute, "Smooth Attribute", "") DefNode(GeometryNode, GEO_NODE_BOUNDING_BOX, 0, "BOUNDING_BOX", BoundBox, "Bounding Box", "Calculate the limits of a geometry's positions and generate a box mesh with those dimensions") DefNode(GeometryNode, GEO_NODE_CAPTURE_ATTRIBUTE, def_geo_attribute_capture,"CAPTURE_ATTRIBUTE", CaptureAttribute, "Capture Attribute", "Store the result of a field on a geometry and output the data as a node socket. Allows remembering or interpolating data as the geometry changes, such as positions before deformation") DefNode(GeometryNode, GEO_NODE_COLLECTION_INFO, def_geo_collection_info, "COLLECTION_INFO", CollectionInfo, "Collection Info", "Retrieve geometry from a collection") diff --git a/source/blender/nodes/geometry/CMakeLists.txt b/source/blender/nodes/geometry/CMakeLists.txt index 31c00cc6b82..c4a4fa39c1d 100644 --- a/source/blender/nodes/geometry/CMakeLists.txt +++ b/source/blender/nodes/geometry/CMakeLists.txt @@ -141,6 +141,7 @@ set(SRC nodes/node_geo_set_shade_smooth.cc nodes/node_geo_set_spline_cyclic.cc nodes/node_geo_set_spline_resolution.cc + nodes/node_geo_smooth_attribute.cc nodes/node_geo_store_named_attribute.cc nodes/node_geo_string_join.cc nodes/node_geo_string_to_curves.cc diff --git a/source/blender/nodes/geometry/nodes/node_geo_smooth_attribute.cc b/source/blender/nodes/geometry/nodes/node_geo_smooth_attribute.cc new file mode 100644 index 00000000000..0ed46420bc6 --- /dev/null +++ b/source/blender/nodes/geometry/nodes/node_geo_smooth_attribute.cc @@ -0,0 +1,900 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ + +/** \file + * Smooth is an algorithm for blending the values of adjacent domain elements. + * For the number of iterations field, values mask are grouped. + * Groups know the difference between each other in the count of repetitions. + * When iterating over groups, each group is iterated over all the next ones. + * For group collection span: + * |A B C D E F G H| + * Iteration: + * A : |A B C D E F G H| + * B : |B C D E F G H| + * C : |C D E F G H| + * D : |D E F G H| + * ... + * Due to this, grouping only by equality to repeat count is cheap. + * + * For curves, the algorithm is more complicated. + * The standard mixing of value and + - indices occurs only for the inner mask. + * Edge values (idnex 0 and size()-1) are smoothed separately. + * This simplifies and facilitates the main loop. + */ + +#include "BLI_index_mask_ops.hh" +#include "BLI_sort.hh" +#include "BLI_task.hh" +#include "BLI_vector_set.hh" + +#include "BLI_packing_task.hh" +#include "BLI_timeit.hh" + +#include "DNA_mesh_types.h" +#include "DNA_meshdata_types.h" + +#include "BKE_attribute_math.hh" +#include "BKE_curves.hh" +#include "BKE_mesh.h" + +#include "UI_interface.h" +#include "UI_resources.h" + +#include "node_geometry_util.hh" + +namespace blender::nodes::node_geo_smooth_attribute_cc { + +static void node_declare(NodeDeclarationBuilder &b) +{ + b.add_input(N_("Value"), "Value_Bool") + .default_value(false) + .supports_field() + .hide_value(); + b.add_input(N_("Value"), "Value_Float") + .default_value(0.0f) + .supports_field() + .hide_value(); + b.add_input(N_("Value"), "Value_Int").default_value(0).supports_field().hide_value(); + b.add_input(N_("Value"), "Value_Vector") + .default_value({0.0f, 0.0f, 0.0f}) + .supports_field() + .hide_value(); + b.add_input(N_("Value"), "Value_Color") + .default_value({0.0f, 0.0f, 0.0f, 1.0f}) + .supports_field() + .hide_value(); + + b.add_input("Factor") + .default_value(0.5f) + .subtype(PROP_FACTOR) + .min(0.0f) + .max(1.0f) + .supports_field() + .description(N_("The power of blending a value with its neighbors in one step")); + b.add_input("Iterations").default_value(1).min(0).supports_field(); + + b.add_input("Selection") + .default_value(true) + .supports_field() + .hide_value() + .description(N_("Smooth only selected the values. Other values are not affected")); + + b.add_output(N_("Value"), "Value_Bool").field_source().dependent_field(); + b.add_output(N_("Value"), "Value_Float").field_source().dependent_field(); + b.add_output(N_("Value"), "Value_Int").field_source().dependent_field(); + b.add_output(N_("Value"), "Value_Vector").field_source().dependent_field(); + b.add_output(N_("Value"), "Value_Color").field_source().dependent_field(); +} + +static void node_layout(uiLayout *layout, bContext *UNUSED(C), PointerRNA *ptr) +{ + uiItemR(layout, ptr, "data_type", 0, "", ICON_NONE); +} + +static void node_init(bNodeTree *UNUSED(tree), bNode *node) +{ + node->custom1 = CD_PROP_FLOAT; +} + +static void node_update(bNodeTree *ntree, bNode *node) +{ + const eCustomDataType data_type = static_cast(node->custom1); + + bNodeSocket *socket_value_bool = (bNodeSocket *)node->inputs.first; + bNodeSocket *socket_value_float = socket_value_bool->next; + bNodeSocket *socket_value_int32 = socket_value_float->next; + bNodeSocket *socket_value_vector = socket_value_int32->next; + bNodeSocket *socket_value_color4f = socket_value_vector->next; + + nodeSetSocketAvailability(ntree, socket_value_bool, data_type == CD_PROP_BOOL); + nodeSetSocketAvailability(ntree, socket_value_float, data_type == CD_PROP_FLOAT); + nodeSetSocketAvailability(ntree, socket_value_int32, data_type == CD_PROP_INT32); + nodeSetSocketAvailability(ntree, socket_value_vector, data_type == CD_PROP_FLOAT3); + nodeSetSocketAvailability(ntree, socket_value_color4f, data_type == CD_PROP_COLOR); + + bNodeSocket *out_socket_value_bool = (bNodeSocket *)node->outputs.first; + bNodeSocket *out_socket_value_float = out_socket_value_bool->next; + bNodeSocket *out_socket_value_int32 = out_socket_value_float->next; + bNodeSocket *out_socket_value_vector = out_socket_value_int32->next; + bNodeSocket *out_socket_value_color4f = out_socket_value_vector->next; + + nodeSetSocketAvailability(ntree, out_socket_value_bool, data_type == CD_PROP_BOOL); + nodeSetSocketAvailability(ntree, out_socket_value_float, data_type == CD_PROP_FLOAT); + nodeSetSocketAvailability(ntree, out_socket_value_int32, data_type == CD_PROP_INT32); + nodeSetSocketAvailability(ntree, out_socket_value_vector, data_type == CD_PROP_FLOAT3); + nodeSetSocketAvailability(ntree, out_socket_value_color4f, data_type == CD_PROP_COLOR); +} + +/* + * A structure for collecting all the data required for a smoothing. + * For a comfortable movement. Passed by value. + */ +struct SmoothCore { + const Span factor; + const VArray selection; + const VArray count; + GMutableSpan buffer; + GMutableSpan output; + const CPPType &type; +}; + +/* + * Smooth algorithm buffer. Created from ranges. Passed by value. + */ +template struct SmoothBuffer { + attribute_math::DefaultMixer write_a; + attribute_math::DefaultMixer write_b; + MutableSpan read_a; + MutableSpan read_b; + + SmoothBuffer(MutableSpan values_a, MutableSpan values_b) + : write_a(values_a, IndexMask(0)), + write_b(values_b, IndexMask(0)), + read_a(values_a), + read_b(values_b) + { + BLI_assert(values_a.size() == values_b.size()); + } + + /* + * Swaps read and write locations. Fast enough to use after every loop iteration. + */ + void swap() + { + std::swap(write_a, write_b); + std::swap(read_a, read_b); + } +}; + +/* + * Smoothing group. Key is the number of iterations for sorting. + * After sorting, each group has the count of iterations to the next grout. + * Passed by value. + */ +struct SmoothGroup { + IndexMask mask; + int count; + int iterate_count; + + enum EndpointTypes : int8_t { + None = 0, + First = 1 << 0, + Last = 1 << 1, + }; + + /* + * Endpoints belong to a group and are handled differently. + */ + int8_t curve_endpoints; +}; + +/* + * The mask can be evaluated for all geometry by feild valuator. + * But for curves, need to compute a separate mask. + * Indexes are local in range. + */ +static IndexMask mask_from_selection(VArray selection, + IndexRange range, + Vector &r_indices) +{ + if (selection.is_single()) { + if (selection.get_internal_single()) { + return IndexMask(range.size()); + } + else { + return IndexMask(0); + } + } + r_indices.reinitialize(range.size()); + IndexMask mask = index_mask_ops::find_indices_from_virtual_array( + range, selection, 1024, r_indices); + + r_indices.resize(mask.size()); + threading::parallel_for(mask.index_range(), 1024, [&](IndexRange l_range) { + for (const int64_t index : l_range) { + r_indices[index] = mask[index] - range.first(); + } + }); + return IndexMask(r_indices.as_span()); +} + +static void create_vertex_to_vertex_map(const Mesh &mesh, Array> &r_map) +{ + const Span edges = mesh.edges(); + r_map.reinitialize(mesh.totvert); + for (const MEdge &edge : edges) { + r_map[edge.v1].append(edge.v2); + r_map[edge.v2].append(edge.v1); + } +} + +static void create_vertex_to_edge_map(const Mesh &mesh, Array> &r_map) +{ + const Span verts = mesh.verts(); + const Span edges = mesh.edges(); + r_map.reinitialize(verts.size()); + for (const int64_t i : edges.index_range()) { + r_map[edges[i].v1].append(i); + r_map[edges[i].v2].append(i); + } +} + +static void create_edge_to_edge_map(const Mesh &mesh, + const IndexMask mask, + Array> &r_map) +{ + r_map.reinitialize(mesh.totedge); + Array> edges_by_vert; + create_vertex_to_edge_map(mesh, edges_by_vert); + + const Span edges = mesh.edges(); + + threading::parallel_for(mask.index_range(), 1024, [&](IndexRange range) { + for (const int self_edge : mask.slice(range)) { + + Vector &self_edges = r_map[self_edge]; + const Vector &connections_vert_1 = edges_by_vert[edges[self_edge].v1]; + const Vector &connections_vert_2 = edges_by_vert[edges[self_edge].v2]; + + self_edges.reserve(connections_vert_1.size() - 1 + connections_vert_2.size() - 1); + + for (const int64_t edge_i : connections_vert_1) { + if (edge_i != self_edge) { + self_edges.append(edge_i); + } + } + for (const int64_t edge_i : connections_vert_2) { + if (edge_i != self_edge) { + self_edges.append(edge_i); + } + } + } + }); +} + +static void create_face_to_edge_map(const Mesh &mesh, Array> &r_map) +{ + const Span polys = mesh.polys(); + const Span loops = mesh.loops(); + r_map.reinitialize(mesh.totedge); + + for (const int poly_i : polys.index_range()) { + const MPoly &poly = polys[poly_i]; + for (const MLoop &loop : loops.slice(poly.loopstart, poly.totloop)) { + r_map[loop.e].append(poly_i); + } + } +} + +static void create_face_to_face_map(const Mesh &mesh, + const IndexMask mask, + Array> &r_map) +{ + const Span polys = mesh.polys(); + const Span loops = mesh.loops(); + r_map.reinitialize(polys.size()); + Array> faces_by_edge; + create_face_to_edge_map(mesh, faces_by_edge); + + threading::parallel_for(mask.index_range(), 1024, [&](IndexRange range) { + for (const int64_t poly_i : mask.slice(range)) { + const MPoly &poly = polys[poly_i]; + for (const MLoop &loop : loops.slice(poly.loopstart, poly.totloop)) { + const int edge_i = loop.e; + if (faces_by_edge[edge_i].size() > 1) { + for (const int64_t neighbor : faces_by_edge[edge_i]) { + if (neighbor != poly_i) { + r_map[poly_i].append(neighbor); + } + } + } + } + } + }); +} + +static void create_mesh_map(const Mesh &mesh, + const eAttrDomain domain, + const IndexMask mask, + Array> &r_map) +{ + switch (domain) { + case ATTR_DOMAIN_POINT: + create_vertex_to_vertex_map(mesh, r_map); + break; + case ATTR_DOMAIN_EDGE: + create_edge_to_edge_map(mesh, mask, r_map); + break; + case ATTR_DOMAIN_FACE: + create_face_to_face_map(mesh, mask, r_map); + break; + default: + BLI_assert_unreachable(); + } +} + +/* + * Param: empty_groups is mask for always empty optional groups. + */ +static Array smooth_groups_evaluate(const VArray &counts, + const IndexRange range, + const IndexMask mask, + const IndexMask empty_groups, + MultiValueMap &r_groups) +{ + if (counts.is_single()) { + if (counts.get_internal_single() > 0) { + /* If count is single and more than 0, smooth groups is actually single group. */ + Array groups(1); + groups[0].mask = mask; + groups[0].count = counts.get_internal_single(); + groups[0].iterate_count = counts.get_internal_single(); + groups[0].curve_endpoints = SmoothGroup::EndpointTypes::None; + return groups; + } + return {}; + } + else { + /* Grouping all mask elements by iterate count keys. */ + int cap = 0; + for (const int64_t i : mask) { + if (const int count = counts[range[i]]; count > 0) { + r_groups.add(count, i); + cap++; + } + } + for (const int64_t i : empty_groups) { + if (const int count = counts[range[i]]; count > 0) { + r_groups.add_multiple(count, {}); + cap++; + } + } + + /* Filling all group by info about mask of smoothing, count, endpoints .*/ + Array groups(r_groups.size()); + int index = 0; + for (const int count : r_groups.keys()) { + groups[index].count = count; + groups[index].mask = IndexMask(r_groups.lookup(count)); + groups[index].curve_endpoints = SmoothGroup::EndpointTypes::None; + index++; + } + + /* Smoothing of each group will do by count order.*/ + parallel_sort(groups.begin(), groups.end(), [](const SmoothGroup &a, const SmoothGroup &b) { + return a.count < b.count; + }); + + /* Field iterate count in value for smoothing. The difference between self and previous smooth + * group iteration. */ + int diff_count = 0; + for (SmoothGroup &group : groups) { + group.iterate_count = group.count - diff_count; + diff_count = group.count; + } + return groups; + } +} + +static Array smooth_groups_evaluate_for_curve(const VArray &count, + const IndexRange range, + const IndexMask mask, + MultiValueMap &r_groups) +{ + IndexMask curve_mask = mask; + const int64_t first_index = 0; + const int64_t last_index = range.size() - 1; + + Vector endpoints; + + const bool first_endpoint_in_mask = mask[0] == first_index; + const bool last_endpoint_in_mask = mask.last() == last_index; + if (first_endpoint_in_mask) { + endpoints.append(first_index); + curve_mask = curve_mask.slice(1, curve_mask.size() - 1); + } + if (last_endpoint_in_mask) { + endpoints.append(last_index); + curve_mask = curve_mask.slice(0, curve_mask.size() - 1); + } + + Array groups = smooth_groups_evaluate( + count, range, curve_mask, endpoints.as_span(), r_groups); + + const int first_endpoint_count = count[range[first_index]]; + const int last_endpoint_count = count[range[last_index]]; + + const bool first_endpoint = (first_endpoint_count > 0) && first_endpoint_in_mask; + const bool last_endpoint = (last_endpoint_count > 0) && last_endpoint_in_mask; + + int first_endpoint_group_index = 0; + int last_endpoint_group_index = 0; + + threading::parallel_invoke( + 1024 < groups.size() && first_endpoint && last_endpoint, + [&]() { + if (first_endpoint) { + for (const int64_t index : groups.index_range()) { + if (groups[index].count == first_endpoint_count) { + first_endpoint_group_index = index; + break; + } + } + } + }, + [&]() { + if (last_endpoint) { + for (const int64_t index : groups.index_range()) { + if (groups[index].count == last_endpoint_count) { + last_endpoint_group_index = index; + break; + } + } + } + }); + + if (first_endpoint) { + groups[first_endpoint_group_index].curve_endpoints |= SmoothGroup::EndpointTypes::First; + } + if (last_endpoint) { + groups[last_endpoint_group_index].curve_endpoints |= SmoothGroup::EndpointTypes::Last; + } + + return groups; +} + +template +static void smooth_mesh_exec(const Span factors, + const Span> map, + const Span groups, + SmoothBuffer buffer) +{ + for (const int64_t group_index : groups.index_range()) { + const Span current_collection = groups.slice(group_index, + groups.size() - group_index); + for ([[maybe_unused]] const int64_t repeat : IndexRange(groups[group_index].iterate_count)) { + threading::parallel_for_each(current_collection, [&](const SmoothGroup group) { + threading::parallel_for(group.mask.index_range(), 1024, [&](const IndexRange range) { + const IndexMask slice = group.mask.slice(range); + for (const int64_t index : slice) { + const float count = float(map[index].size()); + const float factor = factors[index] * count; + buffer.write_a.set(index, buffer.read_b[index], count - factor); + for (const int neighbor : map[index]) { + buffer.write_a.mix_in(index, buffer.read_b[neighbor], factor); + } + } + buffer.write_a.finalize(slice); + }); + }); + buffer.swap(); + } + /* After smoothing, actual values may be required from both buffers in next iteration. Copy. */ + groups[group_index].mask.foreach_index( + [&](const int64_t index) { buffer.read_a[index] = buffer.read_b[index]; }); + } +} + +template +static void smooth_curve_exec(const Span factors, + const Span groups, + SmoothBuffer buffer) +{ + const int64_t first_endpoint = 0; + const int64_t last_endpoint = buffer.read_a.size() - 1; + + const Span first_endpoint_span(&first_endpoint, 1); + const Span last_endpoint_span(&last_endpoint, 1); + + for (const int64_t group_index : groups.index_range()) { + const Span current_collection = groups.slice(group_index, + groups.size() - group_index); + for ([[maybe_unused]] const int64_t repeat : IndexRange(groups[group_index].iterate_count)) { + threading::parallel_for_each(current_collection, [&](const SmoothGroup group) { + threading::parallel_for(group.mask.index_range(), 1024, [&](const IndexRange range) { + const IndexMask slice = group.mask.slice(range); + for (const int64_t index : slice) { + const float factor = factors[index] * 2.0f; + buffer.write_a.set(index, buffer.read_b[index], 2.0f - factor); + buffer.write_a.mix_in(index, buffer.read_b[index + 1], factor); + buffer.write_a.mix_in(index, buffer.read_b[index - 1], factor); + } + buffer.write_a.finalize(slice); + }); + if constexpr (is_cyclic) { + if (group.curve_endpoints & SmoothGroup::EndpointTypes::First) { + const float factor = factors[first_endpoint] * 2.0f; + buffer.write_a.set(first_endpoint, buffer.read_b[first_endpoint], 2.0f - factor); + buffer.write_a.mix_in(first_endpoint, buffer.read_b[first_endpoint + 1], factor); + buffer.write_a.mix_in(first_endpoint, buffer.read_b[last_endpoint], factor); + buffer.write_a.finalize(first_endpoint_span); + } + if (group.curve_endpoints & SmoothGroup::EndpointTypes::Last) { + const float factor = factors[last_endpoint] * 2.0f; + buffer.write_a.set(last_endpoint, buffer.read_b[last_endpoint], 2.0f - factor); + buffer.write_a.mix_in(last_endpoint, buffer.read_b[last_endpoint - 1], factor); + buffer.write_a.mix_in(last_endpoint, buffer.read_b[first_endpoint], factor); + buffer.write_a.finalize(last_endpoint_span); + } + } + else { + if (group.curve_endpoints & SmoothGroup::EndpointTypes::First) { + const float factor = factors[first_endpoint]; + buffer.write_a.set(first_endpoint, buffer.read_b[first_endpoint], 1.0f - factor); + buffer.write_a.mix_in(first_endpoint, buffer.read_b[first_endpoint + 1], factor); + buffer.write_a.finalize(first_endpoint_span); + } + if (group.curve_endpoints & SmoothGroup::EndpointTypes::Last) { + const float factor = factors[last_endpoint]; + buffer.write_a.set(last_endpoint, buffer.read_b[last_endpoint], 1.0f - factor); + buffer.write_a.mix_in(last_endpoint, buffer.read_b[last_endpoint - 1], factor); + buffer.write_a.finalize(last_endpoint_span); + } + } + }); + buffer.swap(); + } + + groups[group_index].mask.foreach_index( + [&](const int64_t index) { buffer.read_a[index] = buffer.read_b[index]; }); + + const SmoothGroup group = groups[group_index]; + if (group.curve_endpoints & SmoothGroup::EndpointTypes::First) { + buffer.read_a[first_endpoint] = buffer.read_b[first_endpoint]; + } + if (group.curve_endpoints & SmoothGroup::EndpointTypes::Last) { + buffer.read_a[last_endpoint] = buffer.read_b[last_endpoint]; + } + } +} + +static void smooth_mesh(const Mesh &mesh, + const int64_t domain_size, + const eAttrDomain domain, + const IndexMask mask, + SmoothCore smooth) +{ + Array groups; + MultiValueMap r_groups; + Array> smooth_map; + threading::parallel_invoke( + 1024 < domain_size, + [&]() { + groups = smooth_groups_evaluate( + std::move(smooth.count), IndexRange(domain_size), mask, {}, r_groups); + }, + [&]() { create_mesh_map(mesh, domain, mask, smooth_map); }); + attribute_math::convert_to_static_type(smooth.type, [&](auto dummy) { + using T = decltype(dummy); + SmoothBuffer buffer(smooth.output.typed(), smooth.buffer.typed()); + smooth_mesh_exec(smooth.factor, smooth_map, groups.as_span(), buffer); + }); +} + +static void smooth_curves1(const bke::CurvesGeometry &curves, SmoothCore smooth) +{ + const VArray cyclic = curves.cyclic(); + + Array curves_points_num(curves.curves_num()); + + for (const int index : curves.curves_range()){ + curves_points_num[index] = curves.points_num_for_curve(index); + } + + packing_task::pack(curves_points_num, curves.points_num() / curves.curves_num(), [&](const Span curves_indices){ + Vector curve_mask; + + for (const int64_t curve_index : curves_indices) { + const IndexRange points = curves.points_for_curve(curve_index); + if (points.size() < 2) { + continue; + } + /* Vector curve_mask reinitialize in mask_from_selection for requisite size if need. */ + const IndexMask mask = mask_from_selection(smooth.selection, points, curve_mask); + if (mask.is_empty()) { + continue; + } + MultiValueMap r_groups; + Array groups = smooth_groups_evaluate_for_curve( + std::move(smooth.count), points, mask, r_groups); + + attribute_math::convert_to_static_type(smooth.type, [&](auto dummy) { + using T = decltype(dummy); + SmoothBuffer buffer(smooth.output.typed().slice(points), + smooth.buffer.typed().slice(points)); + if (cyclic[curve_index]) { + smooth_curve_exec(smooth.factor.slice(points), groups.as_span(), buffer); + } + else { + smooth_curve_exec(smooth.factor.slice(points), groups.as_span(), buffer); + } + }); + } + }); +} + +static void smooth_curves2(const bke::CurvesGeometry &curves, SmoothCore smooth) +{ + const VArray cyclic = curves.cyclic(); + + threading::parallel_for(curves.curves_range(), 1, [&](IndexRange curves_range) { + Vector curve_mask; + + for (const int64_t curve_index : curves_range) { + const IndexRange points = curves.points_for_curve(curve_index); + if (points.size() < 2) { + continue; + } + /* Vector curve_mask reinitialize in mask_from_selection for requisite size if need. */ + const IndexMask mask = mask_from_selection(smooth.selection, points, curve_mask); + if (mask.is_empty()) { + continue; + } + MultiValueMap r_groups; + Array groups = smooth_groups_evaluate_for_curve( + std::move(smooth.count), points, mask, r_groups); + + attribute_math::convert_to_static_type(smooth.type, [&](auto dummy) { + using T = decltype(dummy); + SmoothBuffer buffer(smooth.output.typed().slice(points), + smooth.buffer.typed().slice(points)); + if (cyclic[curve_index]) { + smooth_curve_exec(smooth.factor.slice(points), groups.as_span(), buffer); + } + else { + smooth_curve_exec(smooth.factor.slice(points), groups.as_span(), buffer); + } + }); + } + }); +} +static void smooth_curves3(const bke::CurvesGeometry &curves, SmoothCore smooth) +{ + const VArray cyclic = curves.cyclic(); + + const int points_average = curves.points_num() / curves.curves_num(); + const int grain_size_ = math::clamp(1, 4096, 1024 / points_average); + float grain_slow = grain_size_; + /* Power to reduce the inverse relationship between the number of dots to granulation. Found + * during experiments. */ + for ([[maybe_unused]] const int i : IndexRange(22)) { + grain_slow = sqrtf(grain_slow); + } + const int grain_size = threading::prepair_grain_size(math::clamp(int(grain_slow), 1, 4096)); + threading::parallel_for(curves.curves_range(), grain_size, [&](IndexRange curves_range) { + Vector curve_mask; + + for (const int64_t curve_index : curves_range) { + const IndexRange points = curves.points_for_curve(curve_index); + if (points.size() < 2) { + continue; + } + /* Vector curve_mask reinitialize in mask_from_selection for requisite size if need. */ + const IndexMask mask = mask_from_selection(smooth.selection, points, curve_mask); + if (mask.is_empty()) { + continue; + } + MultiValueMap r_groups; + Array groups = smooth_groups_evaluate_for_curve( + std::move(smooth.count), points, mask, r_groups); + + attribute_math::convert_to_static_type(smooth.type, [&](auto dummy) { + using T = decltype(dummy); + SmoothBuffer buffer(smooth.output.typed().slice(points), + smooth.buffer.typed().slice(points)); + if (cyclic[curve_index]) { + smooth_curve_exec(smooth.factor.slice(points), groups.as_span(), buffer); + } + else { + smooth_curve_exec(smooth.factor.slice(points), groups.as_span(), buffer); + } + }); + } + }); +} + + +class SmoothField final : public bke::GeometryFieldInput { + private: + Field selection_field_; + Field count_field_; + Field factor_field_; + GField value_field_; + + public: + SmoothField(Field selection_field, + Field count_field, + Field factor_field, + GField value_field) + : bke::GeometryFieldInput(value_field.cpp_type(), "Smoothed Attribute"), + selection_field_(std::move(selection_field)), + count_field_(std::move(count_field)), + factor_field_(std::move(factor_field)), + value_field_(std::move(value_field)) + { + } + + GVArray get_varray_for_context(const bke::GeometryFieldContext &context, + const IndexMask mask) const final + { + const int domain_size = context.attributes()->domain_size(context.domain()); + + FieldEvaluator evaluator(context, &mask); + + GArray<> output(*type_, domain_size); + VArray src_selection = VArray::ForSingle(true, domain_size); + /* The selection mask is not required for the mesh. */ + if (context.type() == GEO_COMPONENT_TYPE_CURVE) { + evaluator.add(selection_field_); + } + evaluator.add_with_destination(value_field_, output.as_mutable_span()); + + evaluator.evaluate(); + + if (context.type() == GEO_COMPONENT_TYPE_CURVE) { + src_selection = evaluator.get_evaluated(0); + } + + /* The smoothing function does not work with a graph less than 2x. */ + if (domain_size < 2) { + return GVArray::ForGArray(std::move(output)); + } + + /* If all points of this curve is out of selection, can skip this computing. */ + if (src_selection.is_single() && !src_selection.get_internal_single()) { + return GVArray::ForGArray(std::move(output)); + } + + GArray buffer = output; + + auto clamp_fn = std::make_unique>( + __func__, + [](float factor) { return math::clamp(factor, 0.0f, 1.0f); }, + fn::CustomMF_presets::AllSpanOrSingle()); + Field factor_field_clamped( + FieldOperation::Create(std::move(clamp_fn), {std::move(factor_field_)}), 0); + Array factors(domain_size); + + FieldEvaluator mask_evaluator(context, &mask); + mask_evaluator.add(count_field_); + mask_evaluator.add_with_destination(factor_field_clamped, factors.as_mutable_span()); + mask_evaluator.set_selection(selection_field_); + mask_evaluator.evaluate(); + const VArray src_count = mask_evaluator.get_evaluated(0); + const IndexMask evaluated_mask = mask_evaluator.get_evaluated_selection_as_mask(); + + /* With 0 iterations, there is no effect. */ + if (src_count.is_single() && !src_count.get_internal_single()) { + return GVArray::ForGArray(std::move(output)); + } + + SmoothCore smooth{factors.as_span(), + std::move(src_selection), + std::move(src_count), + output.as_mutable_span(), + buffer.as_mutable_span(), + *type_}; + + switch (context.type()) { + case GEO_COMPONENT_TYPE_MESH: + if (ELEM(context.domain(), ATTR_DOMAIN_POINT, ATTR_DOMAIN_EDGE, ATTR_DOMAIN_FACE)) { + if (const Mesh *mesh = context.mesh()) { + smooth_mesh(*mesh, domain_size, context.domain(), evaluated_mask, std::move(smooth)); + } + } + break; + case GEO_COMPONENT_TYPE_CURVE: + if (context.domain() == ATTR_DOMAIN_POINT) { + const bke::CurvesGeometry &curves = *context.curves(); + { + SCOPED_TIMER_AVERAGED("Smooth 1 - packing"); + smooth_curves1(curves, smooth); + } + { + SCOPED_TIMER_AVERAGED("Smooth 2 - grain size 1"); + smooth_curves1(curves, smooth); + } + { + SCOPED_TIMER_AVERAGED("Smooth 3 - grain size complex"); + smooth_curves1(curves, smooth); + } + + } + break; + default: + break; + } + + return GVArray::ForGArray(std::move(output)); + } + + uint64_t hash() const override + { + return get_default_hash_4(selection_field_, count_field_, factor_field_, value_field_); + } + + bool is_equal_to(const fn::FieldNode &other) const override + { + if (const SmoothField *other_smooth = dynamic_cast(&other)) { + return selection_field_ == other_smooth->selection_field_ && + count_field_ == other_smooth->count_field_ && + factor_field_ == other_smooth->factor_field_ && + value_field_ == other_smooth->value_field_; + } + return false; + } +}; + +static StringRefNull identifier_suffix(eCustomDataType data_type) +{ + switch (data_type) { + case CD_PROP_BOOL: + return "Bool"; + case CD_PROP_FLOAT: + return "Float"; + case CD_PROP_INT32: + return "Int"; + case CD_PROP_COLOR: + return "Color"; + case CD_PROP_FLOAT3: + return "Vector"; + default: + BLI_assert_unreachable(); + return ""; + } +} + +static void node_geo_exec(GeoNodeExecParams params) +{ + const eCustomDataType data_type = static_cast(params.node().custom1); + + Field select_field = params.extract_input>("Selection"); + Field count_field = params.extract_input>("Iterations"); + Field factor_field = params.extract_input>("Factor"); + + attribute_math::convert_to_static_type(data_type, [&](auto dummy) { + using T = decltype(dummy); + static const std::string identifier = "Value_" + identifier_suffix(data_type); + Field value_field = params.extract_input>(identifier); + Field output_field{std::make_shared(std::move(select_field), + std::move(count_field), + std::move(factor_field), + std::move(value_field))}; + params.set_output(identifier, std::move(output_field)); + }); +} + +} // namespace blender::nodes::node_geo_smooth_attribute_cc + +void register_node_type_geo_smooth_attribute() +{ + namespace file_ns = blender::nodes::node_geo_smooth_attribute_cc; + + static bNodeType ntype; + geo_node_type_base(&ntype, GEO_NODE_SMOOTH_ATTRIBUTE, "Smooth Attribute", NODE_CLASS_ATTRIBUTE); + ntype.declare = file_ns::node_declare; + ntype.initfunc = file_ns::node_init; + ntype.updatefunc = file_ns::node_update; + ntype.draw_buttons = file_ns::node_layout; + ntype.geometry_node_execute = file_ns::node_geo_exec; + nodeRegisterType(&ntype); +}