Geometry Nodes: Extrude Mesh Node

This patch introduces an extrude node with three modes. The vertex mode
is quite simple, and just attaches new edges to the selected vertices.
The edge mode attaches new faces to the selected edges. The faces mode
extrudes patches of selected faces, or each selected face individually,
depending on the "Individual" boolean input.

The default value of the "Offset" input is the mesh's normals, which
can be scaled with the "Offset Scale" input.

**Attribute Propagation**
Attributes are transferred to the new elements with specific rules.
Attributes will never change domains for interpolations. Generally
boolean attributes are propagated with "or", meaning any connected
"true" value that is mixed in for other types will cause the new value
to be "true" as well. The `"id"` attribute does not have any special
handling currently.

Vertex Mode
 - Vertex: Copied values of selected vertices.
 - Edge: Averaged values of selected edges. For booleans, edges are
   selected if any connected edges are selected.
Edge Mode
 - Vertex: Copied values of extruded vertices.
 - Connecting edges (vertical): Average values of connected extruded
   edges. For booleans, the edges are selected if any connected
   extruded edges are selected.
 - Duplicate edges: Copied values of selected edges.
 - Face: Averaged values of all faces connected to the selected edge.
   For booleans, faces are selected if any connected original faces
   are selected.
 - Corner: Averaged values of corresponding corners in all faces
   connected to selected edges. For booleans, corners are selected
   if one of those corners are selected.
Face Mode
 - Vertex: Copied values of extruded vertices.
 - Connecting edges (vertical): Average values of connected selected
   edges, not including the edges "on top" of extruded regions.
   For booleans, edges are selected when any connected extruded edges
   were selected.
 - Duplicate edges: Copied values of extruded edges.
 - Face: Copied values of the corresponding selected faces.
 - Corner: Copied values of corresponding corners in selected faces.
Individual Face Mode
 - Vertex: Copied values of extruded vertices.
 - Connecting edges (vertical): Average values of the two neighboring
   edges on each extruded face. For booleans, edges are selected
   when at least one neighbor on the extruded face was selected.
 - Duplicate edges: Copied values of extruded edges.
 - Face: Copied values of the corresponding selected faces.
 - Corner: Copied values of corresponding corners in selected faces.

**Differences from edit mode**
In face mode (non-individual), the behavior can be different than the
extrude tools in edit mode-- this node doesn't handle keeping the back-
faces around in the cases that the edit mode tools do. The planned
"Solidify" node will handle that use case instead. Keeping this node
simpler and faster is preferable at this point, especially because that
sort of "smart" behavior is not that predictable and makes less sense
in a procedural context.

In the future, an "Even Offset" option could be added to this node
hopefully fairly simply. For now it is left out in order to keep
the patch simpler.

**Implementation**
For the implementation, the `Mesh` data structure is used directly
rather than converting to `BMesh` and back like D12224. This optimizes
for large extrusion operations rather than many sequential extrusions.
While this is potentially more verbose, it has some important benefits:
First, there is no conversion to and from `BMesh`. The code only has
to fill arrays and it can do that all at once, making each component of
the algorithm much easier to optimize. It also makes the attribute
interpolation more explicit, and likely faster. Only limited topology
maps must be created in most cases.

While there are some necessary loops and allocations with the size of
the entire mesh, I tried to keep everything I could on the order of the
size of the selection rather than the size of the mesh. In that respect,
the individual faces mode is the best, since there is no topology
information necessary, and the amount of work just depends on the size
of the selection.

Modifying an existing mesh instead of generating a new one was a bit
of a toss-up, but has a few potential benefits:
 - Avoids manually copying over attribute data for original elements.
 - Avoids some overhead of creating a new mesh.
 - Can potentially take advantage of future ammortized mesh growth.
This could be changed easily if it turns out to be the wrong choice.

Differential Revision: https://developer.blender.org/D13709

release/scripts/startup/nodeitems_builtins.py

@@ -142,6 +142,7 @@ def mesh_node_items(context):
         yield NodeItemCustom(draw=lambda self, layout, context: layout.separator())
 
     yield NodeItem("GeometryNodeDualMesh")
+    yield NodeItem("GeometryNodeExtrudeMesh")
     yield NodeItem("GeometryNodeFlipFaces")
     yield NodeItem("GeometryNodeMeshBoolean")
     yield NodeItem("GeometryNodeMeshToCurve")

source/blender/blenkernel/BKE_attribute_math.hh

@@ -230,6 +230,43 @@ template<typename T> class SimpleMixer {
   }
 };
 
+/**
+ * Mixes together booleans with "or" while fitting the same interface as the other
+ * mixers in order to be simpler to use. This mixing method has a few benefits:
+ *  - An "average" for selections is relatively meaningless.
+ *  - Predictable selection propagation is very super important.
+ *  - It's generally  easier to remove an element from a selection that is slightly too large than
+ *    the opposite.
+ */
+class BooleanPropagationMixer {
+ private:
+  MutableSpan<bool> buffer_;
+
+ public:
+  /**
+   * \param buffer: Span where the interpolated values should be stored.
+   */
+  BooleanPropagationMixer(MutableSpan<bool> buffer) : buffer_(buffer)
+  {
+    buffer_.fill(false);
+  }
+
+  /**
+   * Mix a #value into the element with the given #index.
+   */
+  void mix_in(const int64_t index, const bool value, [[maybe_unused]] const float weight = 1.0f)
+  {
+    buffer_[index] |= value;
+  }
+
+  /**
+   * Does not do anything, since the mixing is trivial.
+   */
+  void finalize()
+  {
+  }
+};
+
 /**
  * This mixer accumulates values in a type that is different from the one that is mixed.
  * Some types cannot encode the floating point weights in their values (e.g. int and bool).
@@ -291,7 +328,7 @@ class ColorGeometryMixer {
 };
 
 template<typename T> struct DefaultMixerStruct {
-  /* Use void by default. This can be check for in `if constexpr` statements. */
+  /* Use void by default. This can be checked for in `if constexpr` statements. */
   using type = void;
 };
 template<> struct DefaultMixerStruct<float> {
@@ -327,6 +364,23 @@ template<> struct DefaultMixerStruct<bool> {
   using type = SimpleMixerWithAccumulationType<bool, float, float_to_bool>;
 };
 
+template<typename T> struct DefaultPropatationMixerStruct {
+  /* Use void by default. This can be checked for in `if constexpr` statements. */
+  using type = typename DefaultMixerStruct<T>::type;
+};
+
+template<> struct DefaultPropatationMixerStruct<bool> {
+  using type = BooleanPropagationMixer;
+};
+
+/**
+ * This mixer is meant for propagating attributes when creating new geometry. A key difference
+ * with the default mixer is that booleans are mixed with "or" instead of "at least half"
+ * (the default mixing for booleans).
+ */
+template<typename T>
+using DefaultPropatationMixer = typename DefaultPropatationMixerStruct<T>::type;
+
 /* Utility to get a good default mixer for a given type. This is `void` when there is no default
  * mixer for the given type. */
 template<typename T> using DefaultMixer = typename DefaultMixerStruct<T>::type;

source/blender/blenkernel/BKE_node.h

@@ -1632,6 +1632,7 @@ int ntreeTexExecTree(struct bNodeTree *ntree,
 #define GEO_NODE_CURVE_PRIMITIVE_ARC 1149
 #define GEO_NODE_FLIP_FACES 1150
 #define GEO_NODE_SCALE_ELEMENTS 1151
+#define GEO_NODE_EXTRUDE_MESH 1152
 
 /** \} */
 

source/blender/blenkernel/intern/customdata.cc

@@ -2209,7 +2209,9 @@ void CustomData_realloc(CustomData *data, int totelem)
       continue;
     }
     typeInfo = layerType_getInfo(layer->type);
-    layer->data = MEM_reallocN(layer->data, (size_t)totelem * typeInfo->size);
+    /* Use calloc to avoid the need to manually initialize new data in layers.
+     * Useful for types like #MDeformVert which contain a pointer. */
+    layer->data = MEM_recallocN(layer->data, (size_t)totelem * typeInfo->size);
   }
 }
 

source/blender/blenkernel/intern/node.cc

@@ -4768,6 +4768,7 @@ static void registerGeometryNodes()
   register_node_type_geo_distribute_points_on_faces();
   register_node_type_geo_dual_mesh();
   register_node_type_geo_edge_split();
+  register_node_type_geo_extrude_mesh();
   register_node_type_geo_field_at_index();
   register_node_type_geo_flip_faces();
   register_node_type_geo_geometry_to_instance();

source/blender/makesdna/DNA_node_types.h

@@ -1385,6 +1385,11 @@ typedef struct NodeGeometryPointTranslate {
   uint8_t input_type;
 } NodeGeometryPointTranslate;
 
+typedef struct NodeGeometryExtrudeMesh {
+  /* GeometryNodeExtrudeMeshMode */
+  uint8_t mode;
+} NodeGeometryExtrudeMesh;
+
 typedef struct NodeGeometryObjectInfo {
   /* GeometryNodeTransformSpace. */
   uint8_t transform_space;
@@ -2155,6 +2160,12 @@ typedef enum GeometryNodeDistributePointsOnFacesMode {
   GEO_NODE_POINT_DISTRIBUTE_POINTS_ON_FACES_POISSON = 1,
 } GeometryNodeDistributePointsOnFacesMode;
 
+typedef enum GeometryNodeExtrudeMeshMode {
+  GEO_NODE_EXTRUDE_MESH_VERTICES = 0,
+  GEO_NODE_EXTRUDE_MESH_EDGES = 1,
+  GEO_NODE_EXTRUDE_MESH_FACES = 2,
+} GeometryNodeExtrudeMeshMode;
+
 typedef enum GeometryNodeRotatePointsType {
   GEO_NODE_POINT_ROTATE_TYPE_EULER = 0,
   GEO_NODE_POINT_ROTATE_TYPE_AXIS_ANGLE = 1,

source/blender/makesrna/intern/rna_nodetree.c

@@ -9894,6 +9894,27 @@ static void def_geo_point_distribute(StructRNA *srna)
   RNA_def_property_update(prop, NC_NODE | NA_EDITED, "rna_Node_socket_update");
 }
 
+static void def_geo_extrude_mesh(StructRNA *srna)
+{
+  PropertyRNA *prop;
+
+  static const EnumPropertyItem mode_items[] = {
+      {GEO_NODE_EXTRUDE_MESH_VERTICES, "VERTICES", 0, "Vertices", ""},
+      {GEO_NODE_EXTRUDE_MESH_EDGES, "EDGES", 0, "Edges", ""},
+      {GEO_NODE_EXTRUDE_MESH_FACES, "FACES", 0, "Faces", ""},
+      {0, NULL, 0, NULL, NULL},
+  };
+
+  RNA_def_struct_sdna_from(srna, "NodeGeometryExtrudeMesh", "storage");
+
+  prop = RNA_def_property(srna, "mode", PROP_ENUM, PROP_NONE);
+  RNA_def_property_enum_sdna(prop, NULL, "mode");
+  RNA_def_property_enum_items(prop, mode_items);
+  RNA_def_property_enum_default(prop, GEO_NODE_EXTRUDE_MESH_FACES);
+  RNA_def_property_ui_text(prop, "Mode", "");
+  RNA_def_property_update(prop, NC_NODE | NA_EDITED, "rna_Node_update");
+}
+
 static void def_geo_distribute_points_on_faces(StructRNA *srna)
 {
   PropertyRNA *prop;

source/blender/modifiers/intern/MOD_nodes_evaluator.cc

@@ -381,6 +381,11 @@ static bool get_implicit_socket_input(const SocketRef &socket, void *r_value)
         new (r_value) ValueOrField<float3>(bke::AttributeFieldInput::Create<float3>(side));
         return true;
       }
+      if (bnode.type == GEO_NODE_EXTRUDE_MESH) {
+        new (r_value)
+            ValueOrField<float3>(Field<float3>(std::make_shared<bke::NormalFieldInput>()));
+        return true;
+      }
       new (r_value) ValueOrField<float3>(bke::AttributeFieldInput::Create<float3>("position"));
       return true;
     }

source/blender/nodes/NOD_geometry.h

@@ -99,6 +99,7 @@ void register_node_type_geo_delete_geometry(void);
 void register_node_type_geo_distribute_points_on_faces(void);
 void register_node_type_geo_dual_mesh(void);
 void register_node_type_geo_edge_split(void);
+void register_node_type_geo_extrude_mesh(void);
 void register_node_type_geo_field_at_index(void);
 void register_node_type_geo_flip_faces(void);
 void register_node_type_geo_geometry_to_instance(void);

source/blender/nodes/NOD_static_types.h

@@ -352,6 +352,7 @@ DefNode(GeometryNode, GEO_NODE_DELETE_GEOMETRY, def_geo_delete_geometry, "DELETE
 DefNode(GeometryNode, GEO_NODE_DISTRIBUTE_POINTS_ON_FACES, def_geo_distribute_points_on_faces, "DISTRIBUTE_POINTS_ON_FACES", DistributePointsOnFaces, "Distribute Points on Faces", "")
 DefNode(GeometryNode, GEO_NODE_ACCUMULATE_FIELD, def_geo_accumulate_field, "ACCUMULATE_FIELD", AccumulateField, "Accumulate Field", "")
 DefNode(GeometryNode, GEO_NODE_DUAL_MESH, 0, "DUAL_MESH", DualMesh, "Dual Mesh", "")
+DefNode(GeometryNode, GEO_NODE_EXTRUDE_MESH, def_geo_extrude_mesh, "EXTRUDE_MESH", ExtrudeMesh, "Extrude Mesh", "")
 DefNode(GeometryNode, GEO_NODE_FIELD_AT_INDEX, def_geo_field_at_index, "FIELD_AT_INDEX", FieldAtIndex, "Field at Index", "")
 DefNode(GeometryNode, GEO_NODE_FILL_CURVE, def_geo_curve_fill, "FILL_CURVE", FillCurve, "Fill Curve", "")
 DefNode(GeometryNode, GEO_NODE_FILLET_CURVE, def_geo_curve_fillet, "FILLET_CURVE", FilletCurve, "Fillet Curve", "")

source/blender/nodes/geometry/CMakeLists.txt

@@ -117,6 +117,7 @@ set(SRC
   nodes/node_geo_distribute_points_on_faces.cc
   nodes/node_geo_dual_mesh.cc
   nodes/node_geo_edge_split.cc
+  nodes/node_geo_extrude_mesh.cc
   nodes/node_geo_field_at_index.cc
   nodes/node_geo_flip_faces.cc
   nodes/node_geo_geometry_to_instance.cc