Geometry Nodes: Improve speed of boolean node, use multi-input socket

This commit improves the performance of the node by up to 40% in some
cases when there are only two input meshes, mainly by skipping the
conversion to and from BMesh.

When there are more than two input meshes (note the distinction from
"Geometries", a geometry set can have many mesh instances), the
performance is actually worse, since boolean currently always does
self intersection in that case. Theoretically this could be improved
in the boolean code, or another option is automatically realizing
instances for each input geometry set.

Another improvement is using multi-input sockets for the inputs, which
removes the need to have a separate boolean node for every operation,
which can hopefully simplify some node trees.

The changes necessary for transforms in `mesh_boolean_convert.cc` are
somewhat subtle; they come from the fact that the collecting the
geometry set instances already gives transforms in the local space
of the modifier object. There is also a very small amount of cleanup
to those lines, using `float4x4::identity()`.

This commit also fixes T87078, where overlapping difference meshes
makes the operation not work, though I haven't investigated why.

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

1 files changed, 73 insertions, 91 deletions

diff --git a/source/blender/nodes/geometry/nodes/node_geo_boolean.cc b/source/blender/nodes/geometry/nodes/node_geo_boolean.cc
index 9f331190420..c3017dc2610 100644
--- a/source/blender/nodes/geometry/nodes/node_geo_boolean.cc
+++ b/source/blender/nodes/geometry/nodes/node_geo_boolean.cc
@@ -14,29 +14,30 @@
  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  */
 
-#include "MEM_guardedalloc.h"
-
-#include "BLI_alloca.h"
-#include "BLI_math_matrix.h"
-
 #include "DNA_mesh_types.h"
-#include "DNA_modifier_types.h"
 
-#include "RNA_enum_types.h"
+#include "BKE_mesh.h"
+#include "BKE_mesh_boolean_convert.h"
 
 #include "UI_interface.h"
 #include "UI_resources.h"
 
-#include "BKE_mesh.h"
-
-#include "bmesh.h"
-#include "tools/bmesh_boolean.h"
-
 #include "node_geometry_util.hh"
 
 static bNodeSocketTemplate geo_node_boolean_in[] = {
     {SOCK_GEOMETRY, N_("Geometry 1")},
-    {SOCK_GEOMETRY, N_("Geometry 2")},
+    {SOCK_GEOMETRY,
+     N_("Geometry 2"),
+     0.0f,
+     0.0f,
+     0.0f,
+     0.0f,
+     0.0f,
+     0.0f,
+     PROP_NONE,
+     SOCK_MULTI_INPUT},
+    {SOCK_BOOLEAN, N_("Self Intersection")},
+    {SOCK_BOOLEAN, N_("Hole Tolerant")},
     {-1, ""},
 };
 
@@ -50,109 +51,88 @@ static void geo_node_boolean_layout(uiLayout *layout, bContext *UNUSED(C), Point
   uiItemR(layout, ptr, "operation", 0, "", ICON_NONE);
 }
 
-static int bm_face_isect_pair(BMFace *f, void *UNUSED(user_data))
-{
-  return BM_elem_flag_test(f, BM_ELEM_DRAW) ? 1 : 0;
-}
-
-static Mesh *mesh_boolean_calc(const Mesh *mesh_a, const Mesh *mesh_b, int boolean_mode)
+static void geo_node_boolean_update(bNodeTree *UNUSED(ntree), bNode *node)
 {
-  const BMAllocTemplate allocsize = BMALLOC_TEMPLATE_FROM_ME(mesh_a, mesh_b);
-
-  BMesh *bm;
-  {
-    struct BMeshCreateParams bmesh_create_params = {0};
-    bmesh_create_params.use_toolflags = false;
-    bm = BM_mesh_create(&allocsize, &bmesh_create_params);
-  }
-
-  {
-    struct BMeshFromMeshParams bmesh_from_mesh_params = {0};
-    bmesh_from_mesh_params.calc_face_normal = true;
-    BM_mesh_bm_from_me(bm, mesh_b, &bmesh_from_mesh_params);
-    BM_mesh_bm_from_me(bm, mesh_a, &bmesh_from_mesh_params);
-  }
-
-  const int looptris_tot = poly_to_tri_count(bm->totface, bm->totloop);
-  int tottri;
-  BMLoop *(*looptris)[3] = (BMLoop *
-                            (*)[3])(MEM_malloc_arrayN(looptris_tot, sizeof(*looptris), __func__));
-  BM_mesh_calc_tessellation_beauty(bm, looptris, &tottri);
-
-  const int i_faces_end = mesh_b->totpoly;
-
-  /* We need face normals because of 'BM_face_split_edgenet'
-   * we could calculate on the fly too (before calling split). */
-
-  int i = 0;
-  BMIter iter;
-  BMFace *bm_face;
-  BM_ITER_MESH (bm_face, &iter, bm, BM_FACES_OF_MESH) {
-    normalize_v3(bm_face->no);
+  GeometryNodeBooleanOperation operation = (GeometryNodeBooleanOperation)node->custom1;
 
-    /* Temp tag to test which side split faces are from. */
-    BM_elem_flag_enable(bm_face, BM_ELEM_DRAW);
+  bNodeSocket *geometry_1_socket = (bNodeSocket *)node->inputs.first;
+  bNodeSocket *geometry_2_socket = geometry_1_socket->next;
 
-    i++;
-    if (i == i_faces_end) {
+  switch (operation) {
+    case GEO_NODE_BOOLEAN_INTERSECT:
+    case GEO_NODE_BOOLEAN_UNION:
+      nodeSetSocketAvailability(geometry_1_socket, false);
+      nodeSetSocketAvailability(geometry_2_socket, true);
+      node_sock_label(geometry_2_socket, N_("Geometry"));
+      break;
+    case GEO_NODE_BOOLEAN_DIFFERENCE:
+      nodeSetSocketAvailability(geometry_1_socket, true);
+      nodeSetSocketAvailability(geometry_2_socket, true);
+      node_sock_label(geometry_2_socket, N_("Geometry 2"));
       break;
-    }
   }
+}
 
-  BM_mesh_boolean(
-      bm, looptris, tottri, bm_face_isect_pair, nullptr, 2, false, false, false, boolean_mode);
-
-  Mesh *result = BKE_mesh_from_bmesh_for_eval_nomain(bm, nullptr, mesh_a);
-  BM_mesh_free(bm);
-  result->runtime.cd_dirty_vert |= CD_MASK_NORMAL;
-  MEM_freeN(looptris);
-
-  return result;
+static void geo_node_boolean_init(bNodeTree *UNUSED(tree), bNode *node)
+{
+  node->custom1 = GEO_NODE_BOOLEAN_DIFFERENCE;
 }
 
 namespace blender::nodes {
+
 static void geo_node_boolean_exec(GeoNodeExecParams params)
 {
-  GeometrySet geometry_set_in_a = params.extract_input<GeometrySet>("Geometry 1");
-  GeometrySet geometry_set_in_b = params.extract_input<GeometrySet>("Geometry 2");
-  GeometrySet geometry_set_out;
-
   GeometryNodeBooleanOperation operation = (GeometryNodeBooleanOperation)params.node().custom1;
+  const bool use_self = params.get_input<bool>("Self Intersection");
+  const bool hole_tolerant = params.get_input<bool>("Hole Tolerant");
+
   if (operation < 0 || operation > 2) {
     BLI_assert(false);
-    params.set_output("Geometry", std::move(geometry_set_out));
+    params.set_output("Geometry", std::move(GeometrySet()));
     return;
   }
 
-  /* TODO: Boolean does support an input of multiple meshes. Currently they must all be
-   * converted to BMesh before running the operation though. D9957 will make it possible
-   * to use the mesh structure directly. */
-  geometry_set_in_a = geometry_set_realize_instances(geometry_set_in_a);
-  geometry_set_in_b = geometry_set_realize_instances(geometry_set_in_b);
+  Vector<const Mesh *> meshes;
+  Vector<const float4x4 *> transforms;
+
+  GeometrySet set_a;
+  if (operation == GEO_NODE_BOOLEAN_DIFFERENCE) {
+    set_a = params.extract_input<GeometrySet>("Geometry 1");
+    /* Note that it technically wouldn't be necessary to realize the instances for the first
+     * geometry input, but the boolean code expects the first shape for the difference operation
+     * to be a single mesh. */
+    set_a = geometry_set_realize_instances(set_a);
+    const Mesh *mesh_in_a = set_a.get_mesh_for_read();
+    if (mesh_in_a != nullptr) {
+      meshes.append(mesh_in_a);
+      transforms.append(nullptr);
+    }
+  }
 
-  const Mesh *mesh_in_a = geometry_set_in_a.get_mesh_for_read();
-  const Mesh *mesh_in_b = geometry_set_in_b.get_mesh_for_read();
+  /* The instance transform matrices are owned by the instance group, so we have to
+   * keep all of them around for use during the boolean operation. */
+  Vector<bke::GeometryInstanceGroup> set_groups;
+  Vector<GeometrySet> geometry_sets = params.extract_multi_input<GeometrySet>("Geometry 2");
+  for (const GeometrySet &geometry_set : geometry_sets) {
+    bke::geometry_set_gather_instances(geometry_set, set_groups);
+  }
 
-  if (mesh_in_a == nullptr || mesh_in_b == nullptr) {
-    if (operation == GEO_NODE_BOOLEAN_UNION) {
-      if (mesh_in_a != nullptr) {
-        params.set_output("Geometry", geometry_set_in_a);
+  for (const bke::GeometryInstanceGroup &set_group : set_groups) {
+    const Mesh *mesh_in = set_group.geometry_set.get_mesh_for_read();
+    if (mesh_in != nullptr) {
+      meshes.append_n_times(mesh_in, set_group.transforms.size());
+      for (const int i : set_group.transforms.index_range()) {
+        transforms.append(set_group.transforms.begin() + i);
       }
-      else {
-        params.set_output("Geometry", geometry_set_in_b);
-      }
-    }
-    else {
-      params.set_output("Geometry", geometry_set_in_a);
     }
-    return;
   }
 
-  Mesh *mesh_out = mesh_boolean_calc(mesh_in_a, mesh_in_b, operation);
-  geometry_set_out = GeometrySet::create_with_mesh(mesh_out);
+  Mesh *result = blender::meshintersect::direct_mesh_boolean(
+      meshes, transforms, float4x4::identity(), {}, use_self, hole_tolerant, operation);
 
-  params.set_output("Geometry", std::move(geometry_set_out));
+  params.set_output("Geometry", GeometrySet::create_with_mesh(result));
 }
+
 }  // namespace blender::nodes
 
 void register_node_type_geo_boolean()
@@ -162,6 +142,8 @@ void register_node_type_geo_boolean()
   geo_node_type_base(&ntype, GEO_NODE_BOOLEAN, "Boolean", NODE_CLASS_GEOMETRY, 0);
   node_type_socket_templates(&ntype, geo_node_boolean_in, geo_node_boolean_out);
   ntype.draw_buttons = geo_node_boolean_layout;
+  ntype.updatefunc = geo_node_boolean_update;
+  node_type_init(&ntype, geo_node_boolean_init);
   ntype.geometry_node_execute = blender::nodes::geo_node_boolean_exec;
   nodeRegisterType(&ntype);
 }