Geometry Nodes: Bounding Box Node

This commit adds a simple node to output the min and max of an
axis-aligned bounding box for the input geometry, as well a rectangular
prism mesh created from these values for convenience.

The initial use case for this node is a "bounding box boolean", where
doing the boolean with just a bounding box could be signigicantly
faster, for cases like cutting a hole in a wall for a window. But it's
easy to imagine other cases where it could be useful.

This node supports mesh and point cloud data right now, volume support
will come as a separate patch. Also note that there is plenty of room
to improve the performance of this node through parallelization.

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

9 files changed, 130 insertions, 1 deletions

diff --git a/release/scripts/startup/nodeitems_builtins.py b/release/scripts/startup/nodeitems_builtins.py
index 7e887caf3f2..ab4d9353e1b 100644
--- a/release/scripts/startup/nodeitems_builtins.py
+++ b/release/scripts/startup/nodeitems_builtins.py
@@ -505,6 +505,7 @@ geometry_node_categories = [
         NodeItem("ShaderNodeCombineRGB"),
     ]),
     GeometryNodeCategory("GEO_GEOMETRY", "Geometry", items=[
+        NodeItem("GeometryNodeBoundBox"),
         NodeItem("GeometryNodeTransform"),
         NodeItem("GeometryNodeJoinGeometry"),
     ]),
diff --git a/source/blender/blenkernel/BKE_node.h b/source/blender/blenkernel/BKE_node.h
index 1b229bce574..30c76dc894c 100644
--- a/source/blender/blenkernel/BKE_node.h
+++ b/source/blender/blenkernel/BKE_node.h
@@ -1398,6 +1398,7 @@ int ntreeTexExecTree(struct bNodeTree *ntree,
 #define GEO_NODE_MESH_PRIMITIVE_GRID 1039
 #define GEO_NODE_ATTRIBUTE_MAP_RANGE 1040
 #define GEO_NODE_ATTRIBUTE_CLAMP 1041
+#define GEO_NODE_BOUNDING_BOX 1042
 
 /** \} */
 
diff --git a/source/blender/blenkernel/intern/node.cc b/source/blender/blenkernel/intern/node.cc
index 315ff40289d..496141c9247 100644
--- a/source/blender/blenkernel/intern/node.cc
+++ b/source/blender/blenkernel/intern/node.cc
@@ -4937,6 +4937,7 @@ static void registerGeometryNodes()
   register_node_type_geo_attribute_vector_math();
   register_node_type_geo_attribute_remove();
   register_node_type_geo_boolean();
+  register_node_type_geo_bounding_box();
   register_node_type_geo_collection_info();
   register_node_type_geo_edge_split();
   register_node_type_geo_is_viewport();
diff --git a/source/blender/nodes/CMakeLists.txt b/source/blender/nodes/CMakeLists.txt
index eaf68678f5f..88482b71f68 100644
--- a/source/blender/nodes/CMakeLists.txt
+++ b/source/blender/nodes/CMakeLists.txt
@@ -156,6 +156,7 @@ set(SRC
   geometry/nodes/node_geo_attribute_separate_xyz.cc
   geometry/nodes/node_geo_attribute_vector_math.cc
   geometry/nodes/node_geo_boolean.cc
+  geometry/nodes/node_geo_bounding_box.cc
   geometry/nodes/node_geo_collection_info.cc
   geometry/nodes/node_geo_common.cc
   geometry/nodes/node_geo_edge_split.cc
diff --git a/source/blender/nodes/NOD_geometry.h b/source/blender/nodes/NOD_geometry.h
index 3a26f38d6ba..4ea4fe79504 100644
--- a/source/blender/nodes/NOD_geometry.h
+++ b/source/blender/nodes/NOD_geometry.h
@@ -42,6 +42,7 @@ void register_node_type_geo_attribute_separate_xyz(void);
 void register_node_type_geo_attribute_vector_math(void);
 void register_node_type_geo_attribute_remove(void);
 void register_node_type_geo_boolean(void);
+void register_node_type_geo_bounding_box(void);
 void register_node_type_geo_collection_info(void);
 void register_node_type_geo_edge_split(void);
 void register_node_type_geo_is_viewport(void);
diff --git a/source/blender/nodes/NOD_static_types.h b/source/blender/nodes/NOD_static_types.h
index 0b1efaca502..bf6bf34325a 100644
--- a/source/blender/nodes/NOD_static_types.h
+++ b/source/blender/nodes/NOD_static_types.h
@@ -309,6 +309,7 @@ DefNode(GeometryNode, GEO_NODE_MESH_PRIMITIVE_LINE, def_geo_mesh_line, "MESH_PRI
 DefNode(GeometryNode, GEO_NODE_MESH_PRIMITIVE_GRID, 0, "MESH_PRIMITIVE_GRID", MeshGrid, "Grid", "")
 DefNode(GeometryNode, GEO_NODE_ATTRIBUTE_MAP_RANGE, def_geo_attribute_map_range, "ATTRIBUTE_MAP_RANGE", AttributeMapRange, "Attribute Map Range", "")
 DefNode(GeometryNode, GEO_NODE_ATTRIBUTE_CLAMP, def_geo_attribute_clamp, "ATTRIBUTE_CLAMP", AttributeClamp, "Attribute Clamp", "")
+DefNode(GeometryNode, GEO_NODE_BOUNDING_BOX, 0, "BOUNDING_BOX", BoundBox, "Bounding Box", "")
 
 /* undefine macros */
 #undef DefNode
diff --git a/source/blender/nodes/geometry/node_geometry_util.hh b/source/blender/nodes/geometry/node_geometry_util.hh
index fb80bd08797..ad4f4331b6c 100644
--- a/source/blender/nodes/geometry/node_geometry_util.hh
+++ b/source/blender/nodes/geometry/node_geometry_util.hh
@@ -58,4 +58,6 @@ Mesh *create_cylinder_or_cone_mesh(const float radius_top,
                                    const int verts_num,
                                    const GeometryNodeMeshCircleFillType fill_type);
 
+Mesh *create_cube_mesh(const float size);
+
 }  // namespace blender::nodes
diff --git a/source/blender/nodes/geometry/nodes/node_geo_bounding_box.cc b/source/blender/nodes/geometry/nodes/node_geo_bounding_box.cc
new file mode 100644
index 00000000000..d0d667e27e4
--- /dev/null
+++ b/source/blender/nodes/geometry/nodes/node_geo_bounding_box.cc
@@ -0,0 +1,121 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#include "BLI_task.hh"
+
+#include "BLI_math_matrix.h"
+
+#include "node_geometry_util.hh"
+
+static bNodeSocketTemplate geo_node_bounding_box_in[] = {
+    {SOCK_GEOMETRY, N_("Geometry")},
+    {-1, ""},
+};
+
+static bNodeSocketTemplate geo_node_bounding_box_out[] = {
+    {SOCK_GEOMETRY, N_("Mesh")},
+    {SOCK_VECTOR, N_("Min")},
+    {SOCK_VECTOR, N_("Max")},
+    {-1, ""},
+};
+
+namespace blender::nodes {
+
+using bke::GeometryInstanceGroup;
+
+static void compute_min_max_from_position_and_transform(const GeometryComponent &component,
+                                                        Span<float4x4> transforms,
+                                                        float3 &r_min,
+                                                        float3 &r_max)
+{
+  ReadAttributePtr position_attribute = component.attribute_try_get_for_read("position");
+  if (!position_attribute) {
+    BLI_assert(component.attribute_domain_size(ATTR_DOMAIN_POINT) == 0);
+    return;
+  }
+  Span<float3> positions = position_attribute->get_span<float3>();
+
+  for (const float4x4 &transform : transforms) {
+    for (const float3 &position : positions) {
+      const float3 transformed_position = transform * position;
+      minmax_v3v3_v3(r_min, r_max, transformed_position);
+    }
+  }
+}
+
+static void compute_geometry_set_instances_boundbox(const GeometrySet &geometry_set,
+                                                    float3 &r_min,
+                                                    float3 &r_max)
+{
+  Vector<GeometryInstanceGroup> set_groups;
+  bke::geometry_set_gather_instances(geometry_set, set_groups);
+
+  for (const GeometryInstanceGroup &set_group : set_groups) {
+    const GeometrySet &set = set_group.geometry_set;
+    Span<float4x4> transforms = set_group.transforms;
+
+    if (set.has<PointCloudComponent>()) {
+      compute_min_max_from_position_and_transform(
+          *set.get_component_for_read<PointCloudComponent>(), transforms, r_min, r_max);
+    }
+    if (set.has<MeshComponent>()) {
+      compute_min_max_from_position_and_transform(
+          *set.get_component_for_read<MeshComponent>(), transforms, r_min, r_max);
+    }
+  }
+}
+
+static void geo_node_bounding_box_exec(GeoNodeExecParams params)
+{
+  GeometrySet geometry_set = params.extract_input<GeometrySet>("Geometry");
+
+  float3 min = float3(FLT_MAX);
+  float3 max = float3(-FLT_MAX);
+
+  if (geometry_set.has_instances()) {
+    compute_geometry_set_instances_boundbox(geometry_set, min, max);
+  }
+  else {
+    geometry_set.compute_boundbox_without_instances(&min, &max);
+  }
+
+  if (min == float3(FLT_MAX)) {
+    params.set_output("Mesh", GeometrySet());
+    params.set_output("Min", float3(0));
+    params.set_output("Max", float3(0));
+  }
+  else {
+    const float3 scale = max - min;
+    const float3 center = min + scale / 2.0f;
+    Mesh *mesh = create_cube_mesh(1.0f);
+    transform_mesh(mesh, center, float3(0), scale);
+    params.set_output("Mesh", GeometrySet::create_with_mesh(mesh));
+    params.set_output("Min", min);
+    params.set_output("Max", max);
+  }
+}
+
+}  // namespace blender::nodes
+
+void register_node_type_geo_bounding_box()
+{
+  static bNodeType ntype;
+
+  geo_node_type_base(&ntype, GEO_NODE_BOUNDING_BOX, "Bounding Box", NODE_CLASS_GEOMETRY, 0);
+  node_type_socket_templates(&ntype, geo_node_bounding_box_in, geo_node_bounding_box_out);
+  ntype.geometry_node_execute = blender::nodes::geo_node_bounding_box_exec;
+  nodeRegisterType(&ntype);
+}
diff --git a/source/blender/nodes/geometry/nodes/node_geo_mesh_primitive_cube.cc b/source/blender/nodes/geometry/nodes/node_geo_mesh_primitive_cube.cc
index f8a9bfd2ed1..1d31068653e 100644
--- a/source/blender/nodes/geometry/nodes/node_geo_mesh_primitive_cube.cc
+++ b/source/blender/nodes/geometry/nodes/node_geo_mesh_primitive_cube.cc
@@ -35,7 +35,7 @@ static bNodeSocketTemplate geo_node_mesh_primitive_cube_out[] = {
 
 namespace blender::nodes {
 
-static Mesh *create_cube_mesh(const float size)
+Mesh *create_cube_mesh(const float size)
 {
   const float4x4 transform = float4x4::identity();