Geometry Nodes: Edges to Face Groups Node

Add a new node that groups faces inside of boundary edge regions.
This is the opposite action as the existing "Face Group Boundaries"
node. It's also the same as some of the "Initialize Face Sets"
options in sculpt mode.

Discussion in #102962 has favored "Group" for a name for these
sockets rather than "Set", so that is used here.

Pull Request #104428

release/scripts/startup/bl_ui/node_add_menu_geometry.py

@@ -338,6 +338,7 @@ class NODE_MT_geometry_node_GEO_MESH_READ(Menu):
         node_add_menu.add_node_type(layout, "GeometryNodeInputMeshEdgeAngle")
         node_add_menu.add_node_type(layout, "GeometryNodeInputMeshEdgeNeighbors")
         node_add_menu.add_node_type(layout, "GeometryNodeInputMeshEdgeVertices")
+        node_add_menu.add_node_type(layout, "GeometryNodeEdgesToFaceGroups")
         node_add_menu.add_node_type(layout, "GeometryNodeInputMeshFaceArea")
         node_add_menu.add_node_type(layout, "GeometryNodeInputMeshFaceNeighbors")
         node_add_menu.add_node_type(layout, "GeometryNodeMeshFaceSetBoundaries")

source/blender/blenkernel/BKE_mesh_mapping.h

@@ -353,6 +353,7 @@ Array<Vector<int>> build_vert_to_edge_map(Span<MEdge> edges, int verts_num);
 Array<Vector<int>> build_vert_to_poly_map(Span<MPoly> polys, Span<MLoop> loops, int verts_num);
 Array<Vector<int>> build_vert_to_loop_map(Span<MLoop> loops, int verts_num);
 Array<Vector<int>> build_edge_to_loop_map(Span<MLoop> loops, int edges_num);
+Array<Vector<int, 2>> build_edge_to_poly_map(Span<MPoly> polys, Span<MLoop> loops, int edges_num);
 Vector<Vector<int>> build_edge_to_loop_map_resizable(Span<MLoop> loops, int edges_num);
 
 inline int poly_loop_prev(const MPoly &poly, int loop_i)

source/blender/blenkernel/BKE_node.h

@@ -1534,6 +1534,7 @@ void BKE_nodetree_remove_layer_n(struct bNodeTree *ntree, struct Scene *scene, i
 #define GEO_NODE_BLUR_ATTRIBUTE 1190
 #define GEO_NODE_IMAGE 1191
 #define GEO_NODE_INTERPOLATE_CURVES 1192
+#define GEO_NODE_EDGES_TO_FACE_GROUPS 1193
 
 /** \} */
 

source/blender/blenkernel/intern/mesh_mapping.cc

@@ -610,6 +610,20 @@ Array<Vector<int>> build_edge_to_loop_map(const Span<MLoop> loops, const int edg
   return map;
 }
 
+Array<Vector<int, 2>> build_edge_to_poly_map(const Span<MPoly> polys,
+                                             const Span<MLoop> loops,
+                                             const int edges_num)
+{
+  Array<Vector<int, 2>> map(edges_num);
+  for (const int64_t i : polys.index_range()) {
+    const MPoly &poly = polys[i];
+    for (const MLoop &loop : loops.slice(poly.loopstart, poly.totloop)) {
+      map[loop.e].append(int(i));
+    }
+  }
+  return map;
+}
+
 Vector<Vector<int>> build_edge_to_loop_map_resizable(const Span<MLoop> loops, const int edges_num)
 {
   Vector<Vector<int>> map(edges_num);

source/blender/nodes/NOD_static_types.h

@@ -314,6 +314,7 @@ DefNode(GeometryNode, GEO_NODE_DUAL_MESH, 0, "DUAL_MESH", DualMesh, "Dual Mesh",
 DefNode(GeometryNode, GEO_NODE_DUPLICATE_ELEMENTS, def_geo_duplicate_elements, "DUPLICATE_ELEMENTS", DuplicateElements, "Duplicate Elements", "Generate an arbitrary number copies of each selected input element")
 DefNode(GeometryNode, GEO_NODE_EDGE_PATHS_TO_CURVES, 0, "EDGE_PATHS_TO_CURVES", EdgePathsToCurves, "Edge Paths to Curves", "")
 DefNode(GeometryNode, GEO_NODE_EDGE_PATHS_TO_SELECTION, 0, "EDGE_PATHS_TO_SELECTION", EdgePathsToSelection, "Edge Paths to Selection", "")
+DefNode(GeometryNode, GEO_NODE_EDGES_TO_FACE_GROUPS, 0, "EDGES_TO_FACE_GROUPS", EdgesToFaceGroups, "Edges to Face Groups", "Group faces into regions surrounded by the selected boundary edges")
 DefNode(GeometryNode, GEO_NODE_EVALUATE_AT_INDEX, def_geo_evaluate_at_index, "FIELD_AT_INDEX", FieldAtIndex, "Evaluate at Index", "Retrieve data of other elements in the context's geometry")
 DefNode(GeometryNode, GEO_NODE_EVALUATE_ON_DOMAIN, def_geo_evaluate_on_domain, "FIELD_ON_DOMAIN", FieldOnDomain, "Evaluate on Domain", "Retrieve values from a field on a different domain besides the domain from the context")
 DefNode(GeometryNode, GEO_NODE_EXTRUDE_MESH, def_geo_extrude_mesh, "EXTRUDE_MESH", ExtrudeMesh, "Extrude Mesh", "Generate new vertices, edges, or faces from selected elements and move them based on an offset while keeping them connected by their boundary")

source/blender/nodes/geometry/CMakeLists.txt

@@ -69,6 +69,7 @@ set(SRC
   nodes/node_geo_edge_paths_to_curves.cc
   nodes/node_geo_edge_paths_to_selection.cc
   nodes/node_geo_edge_split.cc
+  nodes/node_geo_edges_to_face_groups.cc
   nodes/node_geo_evaluate_at_index.cc
   nodes/node_geo_evaluate_on_domain.cc
   nodes/node_geo_extrude_mesh.cc

source/blender/nodes/geometry/node_geometry_register.cc

@@ -53,6 +53,7 @@ void register_geometry_nodes()
   register_node_type_geo_edge_paths_to_curves();
   register_node_type_geo_edge_paths_to_selection();
   register_node_type_geo_edge_split();
+  register_node_type_geo_edges_to_face_groups();
   register_node_type_geo_evaluate_at_index();
   register_node_type_geo_evaluate_on_domain();
   register_node_type_geo_extrude_mesh();

source/blender/nodes/geometry/node_geometry_register.hh

@@ -50,6 +50,7 @@ void register_node_type_geo_duplicate_elements();
 void register_node_type_geo_edge_paths_to_curves();
 void register_node_type_geo_edge_paths_to_selection();
 void register_node_type_geo_edge_split();
+void register_node_type_geo_edges_to_face_groups();
 void register_node_type_geo_evaluate_at_index();
 void register_node_type_geo_evaluate_on_domain();
 void register_node_type_geo_extrude_mesh();

source/blender/nodes/geometry/nodes/node_geo_edges_to_face_groups.cc

@@ -0,0 +1,115 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#include "BKE_mesh.h"
+#include "BKE_mesh_mapping.h"
+
+#include "BLI_atomic_disjoint_set.hh"
+
+#include "node_geometry_util.hh"
+
+namespace blender::nodes::node_geo_edges_to_face_groups_cc {
+
+static void node_declare(NodeDeclarationBuilder &b)
+{
+  b.add_input<decl::Bool>("Boundary Edges")
+      .default_value(true)
+      .hide_value()
+      .supports_field()
+      .description(N_("Edges used to split faces into separate groups"));
+  b.add_output<decl::Int>("Face Group ID")
+      .dependent_field()
+      .description(N_("Index of the face group inside each boundary edge region"));
+}
+
+/* Join all uinque unordered combinations of indices. */
+static void join_indices(AtomicDisjointSet &set, const Span<int> indices)
+{
+  for (const int i : indices.index_range()) {
+    for (int j = i + 1; j < indices.size(); j++) {
+      set.join(indices[i], indices[j]);
+    }
+  }
+}
+
+class FaceSetFromBoundariesInput final : public bke::MeshFieldInput {
+ private:
+  Field<bool> non_boundary_edge_field_;
+
+ public:
+  FaceSetFromBoundariesInput(Field<bool> selection)
+      : bke::MeshFieldInput(CPPType::get<int>(), "Edges to Face Groups"),
+        non_boundary_edge_field_(std::move(selection))
+  {
+  }
+
+  GVArray get_varray_for_context(const Mesh &mesh,
+                                 const eAttrDomain domain,
+                                 const IndexMask /*mask*/) const final
+  {
+    const bke::MeshFieldContext context{mesh, ATTR_DOMAIN_EDGE};
+    fn::FieldEvaluator evaluator{context, mesh.totedge};
+    evaluator.add(non_boundary_edge_field_);
+    evaluator.evaluate();
+    const IndexMask non_boundary_edges = evaluator.get_evaluated_as_mask(0);
+
+    const Span<MPoly> polys = mesh.polys();
+    const Span<MLoop> loops = mesh.loops();
+
+    const Array<Vector<int, 2>> edge_to_face_map = bke::mesh_topology::build_edge_to_poly_map(
+        polys, loops, mesh.totedge);
+
+    AtomicDisjointSet islands(polys.size());
+    for (const int edge : non_boundary_edges) {
+      join_indices(islands, edge_to_face_map[edge]);
+    }
+
+    Array<int> output(polys.size());
+    islands.calc_reduced_ids(output);
+
+    return mesh.attributes().adapt_domain(
+        VArray<int>::ForContainer(std::move(output)), ATTR_DOMAIN_FACE, domain);
+  }
+
+  uint64_t hash() const override
+  {
+    return non_boundary_edge_field_.hash();
+  }
+
+  bool is_equal_to(const fn::FieldNode &other) const override
+  {
+    if (const auto *other_field = dynamic_cast<const FaceSetFromBoundariesInput *>(&other)) {
+      return other_field->non_boundary_edge_field_ == non_boundary_edge_field_;
+    }
+    return false;
+  }
+
+  std::optional<eAttrDomain> preferred_domain(const Mesh & /*mesh*/) const final
+  {
+    return ATTR_DOMAIN_FACE;
+  }
+};
+
+static void geo_node_exec(GeoNodeExecParams params)
+{
+  Field<bool> boundary_edges = params.extract_input<Field<bool>>("Boundary Edges");
+  Field<bool> non_boundary_edges = fn::invert_boolean_field(std::move(boundary_edges));
+  params.set_output(
+      "Face Group ID",
+      Field<int>(std::make_shared<FaceSetFromBoundariesInput>(std::move(non_boundary_edges))));
+}
+
+}  // namespace blender::nodes::node_geo_edges_to_face_groups_cc
+
+void register_node_type_geo_edges_to_face_groups()
+{
+  namespace file_ns = blender::nodes::node_geo_edges_to_face_groups_cc;
+
+  static bNodeType ntype;
+
+  geo_node_type_base(
+      &ntype, GEO_NODE_EDGES_TO_FACE_GROUPS, "Edges to Face Groups", NODE_CLASS_INPUT);
+  ntype.geometry_node_execute = file_ns::geo_node_exec;
+  ntype.declare = file_ns::node_declare;
+
+  nodeRegisterType(&ntype);
+}

source/blender/nodes/geometry/nodes/node_geo_extrude_mesh.cc

@@ -10,6 +10,7 @@
 
 #include "BKE_attribute_math.hh"
 #include "BKE_mesh.h"
+#include "BKE_mesh_mapping.h"
 #include "BKE_mesh_runtime.h"
 
 #include "UI_interface.h"
@@ -288,22 +289,6 @@ static void extrude_mesh_vertices(Mesh &mesh,
   BKE_mesh_runtime_clear_cache(&mesh);
 }
 
-static Array<Vector<int, 2>> mesh_calculate_polys_of_edge(const Mesh &mesh)
-{
-  const Span<MPoly> polys = mesh.polys();
-  const Span<MLoop> loops = mesh.loops();
-  Array<Vector<int, 2>> polys_of_edge(mesh.totedge);
-
-  for (const int i_poly : polys.index_range()) {
-    const MPoly &poly = polys[i_poly];
-    for (const MLoop &loop : loops.slice(poly.loopstart, poly.totloop)) {
-      polys_of_edge[loop.e].append(i_poly);
-    }
-  }
-
-  return polys_of_edge;
-}
-
 static void fill_quad_consistent_direction(Span<MLoop> other_poly_loops,
                                            MutableSpan<MLoop> new_loops,
                                            const int vert_connected_to_poly_1,
@@ -382,7 +367,8 @@ static void extrude_mesh_edges(Mesh &mesh,
     return;
   }
 
-  const Array<Vector<int, 2>> edge_to_poly_map = mesh_calculate_polys_of_edge(mesh);
+  const Array<Vector<int, 2>> edge_to_poly_map = bke::mesh_topology::build_edge_to_poly_map(
+      orig_polys, mesh.loops(), mesh.totedge);
 
   /* Find the offsets on the vertex domain for translation. This must be done before the mesh's
    * custom data layers are reallocated, in case the virtual array references one of them. */
@@ -684,7 +670,8 @@ static void extrude_mesh_face_regions(Mesh &mesh,
   }
 
   /* All of the faces (selected and deselected) connected to each edge. */
-  const Array<Vector<int, 2>> edge_to_poly_map = mesh_calculate_polys_of_edge(mesh);
+  const Array<Vector<int, 2>> edge_to_poly_map = bke::mesh_topology::build_edge_to_poly_map(
+      orig_polys, orig_loops, orig_edges.size());
 
   /* All vertices that are connected to the selected polygons.
    * Start the size at one vert per poly to reduce unnecessary reallocation. */