Geometry Nodes: Multi-Input Sockets

Normally sockets only have one input link. This commit adds the back-end
changes needed to use multiple input links per socket.

Multi-input sockets can be defined with a new flag in `bNodeSocketType`.
The changes necessary to make the sockets work in the geometry nodes
evaluator are generalizing input socket values as a vector of values,
and supporting this in the derived node tree structure.

This patch should contain no functional changes. Two upcoming patches
will use this system for the "Join Geometry" node and expose link picking
and updated display in the UI: D10069 and D10181.

Reviewed By: Jacques Lucke, Hans Goudey

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

9 files changed, 159 insertions, 52 deletions

diff --git a/source/blender/blenkernel/intern/node.cc b/source/blender/blenkernel/intern/node.cc
index 4f9557298c7..2dbfa85b8e1 100644
--- a/source/blender/blenkernel/intern/node.cc
+++ b/source/blender/blenkernel/intern/node.cc
@@ -3549,6 +3549,9 @@ void nodeSetSocketAvailability(bNodeSocket *sock, bool is_available)
 int nodeSocketLinkLimit(const bNodeSocket *sock)
 {
   bNodeSocketType *stype = sock->typeinfo;
+  if (sock->flag & SOCK_MULTI_INPUT) {
+    return 4095;
+  }
   if (stype != nullptr && stype->use_link_limits_of_type) {
     int limit = (sock->in_out == SOCK_IN) ? stype->input_link_limit : stype->output_link_limit;
     return limit;
diff --git a/source/blender/editors/space_node/node_intern.h b/source/blender/editors/space_node/node_intern.h
index a2b04fa9665..51333fd5a09 100644
--- a/source/blender/editors/space_node/node_intern.h
+++ b/source/blender/editors/space_node/node_intern.h
@@ -51,6 +51,7 @@ typedef struct bNodeLinkDrag {
    * This way the links can be added to the node tree while being stored in this list.
    */
   ListBase links;
+  bool from_multi_input_socket;
   int in_out;
 } bNodeLinkDrag;
 
diff --git a/source/blender/editors/space_node/node_relationships.c b/source/blender/editors/space_node/node_relationships.c
index ee7c8bca2f8..0744adb1371 100644
--- a/source/blender/editors/space_node/node_relationships.c
+++ b/source/blender/editors/space_node/node_relationships.c
@@ -836,31 +836,38 @@ static bNodeLinkDrag *node_link_init(Main *bmain, SpaceNode *snode, float cursor
     nldrag = MEM_callocN(sizeof(bNodeLinkDrag), "drag link op customdata");
 
     const int num_links = nodeCountSocketLinks(snode->edittree, sock);
-    int link_limit = nodeSocketLinkLimit(sock);
-    if (num_links > 0 && (num_links >= link_limit || detach)) {
+    if (num_links > 0) {
       /* dragged links are fixed on output side */
       nldrag->in_out = SOCK_OUT;
       /* detach current links and store them in the operator data */
+      bNodeLink *link_to_pick;
       LISTBASE_FOREACH_MUTABLE (bNodeLink *, link, &snode->edittree->links) {
         if (link->tosock == sock) {
-          LinkData *linkdata = MEM_callocN(sizeof(LinkData), "drag link op link data");
-          bNodeLink *oplink = MEM_callocN(sizeof(bNodeLink), "drag link op link");
-          linkdata->data = oplink;
-          *oplink = *link;
-          oplink->next = oplink->prev = NULL;
-          oplink->flag |= NODE_LINK_VALID;
-          oplink->flag &= ~NODE_LINK_TEST;
-          if (node_connected_to_output(bmain, snode->edittree, link->tonode)) {
-            oplink->flag |= NODE_LINK_TEST;
+          if (sock->flag & SOCK_MULTI_INPUT) {
+            nldrag->from_multi_input_socket = true;
           }
+          link_to_pick = link;
+        }
+      }
 
-          BLI_addtail(&nldrag->links, linkdata);
-          nodeRemLink(snode->edittree, link);
+      if (link_to_pick != NULL && !nldrag->from_multi_input_socket) {
+        LinkData *linkdata = MEM_callocN(sizeof(LinkData), "drag link op link data");
+        bNodeLink *oplink = MEM_callocN(sizeof(bNodeLink), "drag link op link");
+        linkdata->data = oplink;
+        *oplink = *link_to_pick;
+        oplink->next = oplink->prev = NULL;
+        oplink->flag |= NODE_LINK_VALID;
+        oplink->flag &= ~NODE_LINK_TEST;
+        if (node_connected_to_output(bmain, snode->edittree, link_to_pick->tonode)) {
+          oplink->flag |= NODE_LINK_TEST;
+        }
 
-          /* send changed event to original link->tonode */
-          if (node) {
-            snode_update(snode, node);
-          }
+        BLI_addtail(&nldrag->links, linkdata);
+        nodeRemLink(snode->edittree, link_to_pick);
+
+        /* send changed event to original link->tonode */
+        if (node) {
+          snode_update(snode, node);
         }
       }
     }
@@ -896,6 +903,8 @@ static int node_link_invoke(bContext *C, wmOperator *op, const wmEvent *event)
 
   float cursor[2];
   UI_view2d_region_to_view(&region->v2d, event->mval[0], event->mval[1], &cursor[0], &cursor[1]);
+  RNA_float_set_array(op->ptr, "drag_start", cursor);
+  RNA_boolean_set(op->ptr, "has_link_picked", false);
 
   ED_preview_kill_jobs(CTX_wm_manager(C), bmain);
 
@@ -941,7 +950,28 @@ void NODE_OT_link(wmOperatorType *ot)
   /* flags */
   ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO | OPTYPE_BLOCKING;
 
+  PropertyRNA *prop;
+
   RNA_def_boolean(ot->srna, "detach", false, "Detach", "Detach and redirect existing links");
+  prop = RNA_def_boolean(
+      ot->srna,
+      "has_link_picked",
+      false,
+      "Has Link Picked",
+      "The operation has placed a link. Only used for multi-input sockets, where the "
+      "link is picked later");
+  RNA_def_property_flag(prop, PROP_HIDDEN);
+  RNA_def_float_array(ot->srna,
+                      "drag_start",
+                      2,
+                      0,
+                      -UI_PRECISION_FLOAT_MAX,
+                      UI_PRECISION_FLOAT_MAX,
+                      "Drag Start",
+                      "The position of the mouse cursor at the start of the operation.",
+                      -UI_PRECISION_FLOAT_MAX,
+                      UI_PRECISION_FLOAT_MAX);
+  RNA_def_property_flag(prop, PROP_HIDDEN);
 }
 
 /* ********************** Make Link operator ***************** */
diff --git a/source/blender/makesdna/DNA_node_types.h b/source/blender/makesdna/DNA_node_types.h
index c4d8c33ce7a..a69af18ded2 100644
--- a/source/blender/makesdna/DNA_node_types.h
+++ b/source/blender/makesdna/DNA_node_types.h
@@ -200,6 +200,8 @@ typedef enum eNodeSocketFlag {
   SOCK_NO_INTERNAL_LINK = (1 << 9),
   /** Draw socket in a more compact form. */
   SOCK_COMPACT = (1 << 10),
+  /** Make the input socket accept multiple incoming links in the UI. */
+  SOCK_MULTI_INPUT = (1 << 11),
 } eNodeSocketFlag;
 
 /* limit data in bNode to what we want to see saved? */
diff --git a/source/blender/modifiers/intern/MOD_nodes.cc b/source/blender/modifiers/intern/MOD_nodes.cc
index 6ce288e8ac5..74cfcefc842 100644
--- a/source/blender/modifiers/intern/MOD_nodes.cc
+++ b/source/blender/modifiers/intern/MOD_nodes.cc
@@ -215,7 +215,7 @@ static bool isDisabled(const struct Scene *UNUSED(scene),
 class GeometryNodesEvaluator {
  private:
   blender::LinearAllocator<> allocator_;
-  Map<const DInputSocket *, GMutablePointer> value_by_input_;
+  Map<std::pair<const DInputSocket *, const DOutputSocket *>, GMutablePointer> value_by_input_;
   Vector<const DInputSocket *> group_outputs_;
   blender::nodes::MultiFunctionByNode &mf_by_node_;
   const blender::nodes::DataTypeConversions &conversions_;
@@ -246,8 +246,8 @@ class GeometryNodesEvaluator {
   {
     Vector<GMutablePointer> results;
     for (const DInputSocket *group_output : group_outputs_) {
-      GMutablePointer result = this->get_input_value(*group_output);
-      results.append(result);
+      Vector<GMutablePointer> result = this->get_input_values(*group_output);
+      results.append(result[0]);
     }
     for (GMutablePointer value : value_by_input_.values()) {
       value.destruct();
@@ -256,32 +256,53 @@ class GeometryNodesEvaluator {
   }
 
  private:
-  GMutablePointer get_input_value(const DInputSocket &socket_to_compute)
+  Vector<GMutablePointer> get_input_values(const DInputSocket &socket_to_compute)
   {
-    std::optional<GMutablePointer> value = value_by_input_.pop_try(&socket_to_compute);
-    if (value.has_value()) {
-      /* This input has been computed before, return it directly. */
-      return *value;
-    }
 
     Span<const DOutputSocket *> from_sockets = socket_to_compute.linked_sockets();
     Span<const DGroupInput *> from_group_inputs = socket_to_compute.linked_group_inputs();
     const int total_inputs = from_sockets.size() + from_group_inputs.size();
-    BLI_assert(total_inputs <= 1);
 
     if (total_inputs == 0) {
       /* The input is not connected, use the value from the socket itself. */
-      return get_unlinked_input_value(socket_to_compute);
+      return {get_unlinked_input_value(socket_to_compute)};
     }
+
     if (from_group_inputs.size() == 1) {
-      /* The input gets its value from the input of a group that is not further connected. */
-      return get_unlinked_input_value(socket_to_compute);
+      return {get_unlinked_input_value(socket_to_compute)};
+    }
+
+    /* Multi-input sockets contain a vector of inputs. */
+    if (socket_to_compute.is_multi_input_socket()) {
+      Vector<GMutablePointer> values;
+      for (const DOutputSocket *from_socket : from_sockets) {
+        const std::pair<const DInputSocket *, const DOutputSocket *> key = std::make_pair(
+            &socket_to_compute, from_socket);
+        std::optional<GMutablePointer> value = value_by_input_.pop_try(key);
+        if (value.has_value()) {
+          values.append(value.value());
+        }
+        else {
+          this->compute_output_and_forward(*from_socket);
+          GMutablePointer value = value_by_input_.pop(key);
+          values.append(value);
+        }
+      }
+      return values;
     }
 
-    /* Compute the socket now. */
     const DOutputSocket &from_socket = *from_sockets[0];
+    const std::pair<const DInputSocket *, const DOutputSocket *> key = std::make_pair(
+        &socket_to_compute, &from_socket);
+    std::optional<GMutablePointer> value = value_by_input_.pop_try(key);
+    if (value.has_value()) {
+      /* This input has been computed before, return it directly. */
+      return {*value};
+    }
+
+    /* Compute the socket now. */
     this->compute_output_and_forward(from_socket);
-    return value_by_input_.pop(&socket_to_compute);
+    return {value_by_input_.pop(key)};
   }
 
   void compute_output_and_forward(const DOutputSocket &socket_to_compute)
@@ -302,8 +323,14 @@ class GeometryNodesEvaluator {
     GValueMap<StringRef> node_inputs_map{allocator_};
     for (const DInputSocket *input_socket : node.inputs()) {
       if (input_socket->is_available()) {
-        GMutablePointer value = this->get_input_value(*input_socket);
-        node_inputs_map.add_new_direct(input_socket->identifier(), value);
+        Vector<GMutablePointer> values = this->get_input_values(*input_socket);
+        for (int i = 0; i < values.size(); ++i) {
+          /* Values from Multi Input Sockets are stored in input map with the format
+           * <identifier>[<index>]. */
+          blender::StringRefNull key = allocator_.copy_string(
+              input_socket->identifier() + (i > 0 ? ("[" + std::to_string(i)) + "]" : ""));
+          node_inputs_map.add_new_direct(key, std::move(values[i]));
+        }
       }
     }
 
@@ -393,13 +420,15 @@ class GeometryNodesEvaluator {
 
   void forward_to_inputs(const DOutputSocket &from_socket, GMutablePointer value_to_forward)
   {
+    /* For all sockets that are linked with the from_socket push the value to their node. */
     Span<const DInputSocket *> to_sockets_all = from_socket.linked_sockets();
 
     const CPPType &from_type = *value_to_forward.type();
-
     Vector<const DInputSocket *> to_sockets_same_type;
     for (const DInputSocket *to_socket : to_sockets_all) {
       const CPPType &to_type = *blender::nodes::socket_cpp_type_get(*to_socket->typeinfo());
+      const std::pair<const DInputSocket *, const DOutputSocket *> key = std::make_pair(
+          to_socket, &from_socket);
       if (from_type == to_type) {
         to_sockets_same_type.append(to_socket);
       }
@@ -411,7 +440,7 @@ class GeometryNodesEvaluator {
         else {
           to_type.copy_to_uninitialized(to_type.default_value(), buffer);
         }
-        value_by_input_.add_new(to_socket, GMutablePointer{to_type, buffer});
+        add_value_to_input_socket(key, GMutablePointer{to_type, buffer});
       }
     }
 
@@ -422,23 +451,35 @@ class GeometryNodesEvaluator {
     else if (to_sockets_same_type.size() == 1) {
       /* This value is only used on one input socket, no need to copy it. */
       const DInputSocket *to_socket = to_sockets_same_type[0];
-      value_by_input_.add_new(to_socket, value_to_forward);
+      const std::pair<const DInputSocket *, const DOutputSocket *> key = std::make_pair(
+          to_socket, &from_socket);
+
+      add_value_to_input_socket(key, value_to_forward);
     }
     else {
       /* Multiple inputs use the value, make a copy for every input except for one. */
       const DInputSocket *first_to_socket = to_sockets_same_type[0];
       Span<const DInputSocket *> other_to_sockets = to_sockets_same_type.as_span().drop_front(1);
       const CPPType &type = *value_to_forward.type();
-
-      value_by_input_.add_new(first_to_socket, value_to_forward);
+      const std::pair<const DInputSocket *, const DOutputSocket *> first_key = std::make_pair(
+          first_to_socket, &from_socket);
+      add_value_to_input_socket(first_key, value_to_forward);
       for (const DInputSocket *to_socket : other_to_sockets) {
+        const std::pair<const DInputSocket *, const DOutputSocket *> key = std::make_pair(
+            to_socket, &from_socket);
         void *buffer = allocator_.allocate(type.size(), type.alignment());
         type.copy_to_uninitialized(value_to_forward.get(), buffer);
-        value_by_input_.add_new(to_socket, GMutablePointer{type, buffer});
+        add_value_to_input_socket(key, GMutablePointer{type, buffer});
       }
     }
   }
 
+  void add_value_to_input_socket(const std::pair<const DInputSocket *, const DOutputSocket *> key,
+                                 GMutablePointer value)
+  {
+    value_by_input_.add_new(key, value);
+  }
+
   GMutablePointer get_unlinked_input_value(const DInputSocket &socket)
   {
     bNodeSocket *bsocket;
diff --git a/source/blender/nodes/NOD_derived_node_tree.hh b/source/blender/nodes/NOD_derived_node_tree.hh
index 4d594a77ebc..62affe43895 100644
--- a/source/blender/nodes/NOD_derived_node_tree.hh
+++ b/source/blender/nodes/NOD_derived_node_tree.hh
@@ -80,6 +80,7 @@ class DInputSocket : public DSocket {
  private:
   Vector<DOutputSocket *> linked_sockets_;
   Vector<DGroupInput *> linked_group_inputs_;
+  bool is_multi_input_socket_;
 
   friend DerivedNodeTree;
 
@@ -90,6 +91,7 @@ class DInputSocket : public DSocket {
   Span<const DGroupInput *> linked_group_inputs() const;
 
   bool is_linked() const;
+  bool is_multi_input_socket() const;
 };
 
 class DOutputSocket : public DSocket {
@@ -362,6 +364,11 @@ inline bool DInputSocket::is_linked() const
   return linked_sockets_.size() > 0 || linked_group_inputs_.size() > 0;
 }
 
+inline bool DInputSocket::is_multi_input_socket() const
+{
+  return is_multi_input_socket_;
+}
+
 /* --------------------------------------------------------------------
  * DOutputSocket inline methods.
  */
diff --git a/source/blender/nodes/NOD_geometry_exec.hh b/source/blender/nodes/NOD_geometry_exec.hh
index 454c9e96246..91d46e3951f 100644
--- a/source/blender/nodes/NOD_geometry_exec.hh
+++ b/source/blender/nodes/NOD_geometry_exec.hh
@@ -104,6 +104,25 @@ class GeoNodeExecParams {
   }
 
   /**
+   * Get input as vector for multi input socket with the given identifier.
+   *
+   * This method can only be called once for each identifier.
+   */
+  template<typename T> Vector<T> extract_multi_input(StringRef identifier)
+  {
+    Vector<T> values;
+    values.append(input_values_.extract<T>(identifier));
+    int i = 1;
+    std::string sub_identifier = identifier + "[1]";
+    while (input_values_.contains(sub_identifier)) {
+      values.append(input_values_.extract<T>(sub_identifier));
+      i++;
+      sub_identifier = identifier + "[" + std::to_string(i) + "]";
+    }
+    return values;
+  }
+
+  /**
    * Get the input value for the input socket with the given identifier.
    *
    * This makes a copy of the value, which is fine for most types but should be avoided for
diff --git a/source/blender/nodes/intern/derived_node_tree.cc b/source/blender/nodes/intern/derived_node_tree.cc
index c693047ff40..f5a0e14f18b 100644
--- a/source/blender/nodes/intern/derived_node_tree.cc
+++ b/source/blender/nodes/intern/derived_node_tree.cc
@@ -91,7 +91,7 @@ DNode &DerivedNodeTree::create_node(const NodeRef &node_ref,
   for (int i : node.inputs_.index_range()) {
     const InputSocketRef &socket_ref = node_ref.input(i);
     DInputSocket &socket = *node.inputs_[i];
-
+    socket.is_multi_input_socket_ = socket_ref.bsocket()->flag & SOCK_MULTI_INPUT;
     socket.id_ = UNINITIALIZED_ID;
     socket.node_ = &node;
     socket.socket_ref_ = &socket_ref;
diff --git a/source/blender/nodes/intern/node_util.c b/source/blender/nodes/intern/node_util.c
index 9669dc6496b..c7c3ced4e56 100644
--- a/source/blender/nodes/intern/node_util.c
+++ b/source/blender/nodes/intern/node_util.c
@@ -281,25 +281,30 @@ static int node_count_links(bNodeTree *ntree, bNodeSocket *sock)
   return count;
 }
 
-/* find an eligible socket for linking */
+/* Find an eligible socket for linking. */
 static bNodeSocket *node_find_linkable_socket(bNodeTree *ntree, bNode *node, bNodeSocket *cur)
 {
-  /* link swapping: try to find a free slot with a matching name */
-
   bNodeSocket *first = cur->in_out == SOCK_IN ? node->inputs.first : node->outputs.first;
   bNodeSocket *sock;
 
-  sock = cur->next ? cur->next : first; /* wrap around the list end */
+  /* Iterate over all sockets of the target node, to find one that matches the same socket type.
+   * The idea behind this is: When a user connects an input to a socket that is
+   * already linked (and if its not an Multi Input Socket), we try to find a replacement socket for
+   * the link that we try to overwrite and connect that previous link to the new socket. */
+  sock = cur->next ? cur->next : first; /* Wrap around the list end. */
   while (sock != cur) {
     if (!nodeSocketIsHidden(sock) && node_link_socket_match(sock, cur)) {
-      int link_count = node_count_links(ntree, sock);
-      /* take +1 into account since we would add a new link */
-      if (link_count + 1 <= nodeSocketLinkLimit(sock)) {
-        return sock; /* found a valid free socket we can swap to */
-      }
+      break;
     }
+    sock = sock->next ? sock->next : first; /* Wrap around the list end. */
+  }
 
-    sock = sock->next ? sock->next : first; /* wrap around the list end */
+  if (!nodeSocketIsHidden(sock) && node_link_socket_match(sock, cur)) {
+    int link_count = node_count_links(ntree, sock);
+    /* Take +1 into account since we would add a new link. */
+    if (link_count + 1 <= nodeSocketLinkLimit(sock)) {
+      return sock; /* Found a valid free socket we can swap to. */
+    }
   }
   return NULL;
 }
@@ -309,7 +314,6 @@ void node_insert_link_default(bNodeTree *ntree, bNode *node, bNodeLink *link)
   bNodeSocket *sock = link->tosock;
   bNodeLink *tlink, *tlink_next;
 
-  /* inputs can have one link only, outputs can have unlimited links */
   if (node != link->tonode) {
     return;
   }