blender
/
blender
129
398
Fork 572
Code Issues 6.2k Pull Requests 747 Projects 19 Wiki Activity

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
This commit is contained in:
Hans Goudey 2021-04-01 15:00:47 -05:00
parent 76cdcc2bca
commit e8573a59f6
Notes: blender-bot 2023-02-13 19:06:03 +01:00 
Referenced by issue #87078, Geometry nodes boolean intersect sometimes not working
5 changed files with 169 additions and 157 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

21
source/blender/blenkernel/BKE_mesh_boolean_convert.h
View File

@ -29,6 +29,7 @@ extern "C" {
Mesh *BKE_mesh_boolean(const Mesh **meshes,
const float (*obmats[])[4][4],
const float (*target_transform)[4][4],
const short **material_remaps,
const int meshes_len,
const bool use_self,
@ -38,3 +39,23 @@ Mesh *BKE_mesh_boolean(const Mesh **meshes,
#ifdef __cplusplus
}
#endif
#ifdef __cplusplus
# include "BLI_float4x4.hh"
# include "BLI_mesh_boolean.hh"
# include "BLI_span.hh"
namespace blender::meshintersect {
Mesh *direct_mesh_boolean(blender::Span<const Mesh *> meshes,
blender::Span<const float4x4 *> obmats,
const float4x4 &target_transform,
blender::Span<const short *> material_remaps,
const bool use_self,
const bool hole_tolerant,
const int boolean_mode);
} // namespace blender::meshintersect
#endif

130
source/blender/blenkernel/intern/mesh_boolean_convert.cc
View File

@ -51,8 +51,9 @@ constexpr int estimated_max_facelen = 100; /* Used for initial size of some Vect
* so this is a hack to clean up such matrices.
* Would be better to change the transformation code itself.
*/
static void clean_obmat(float4x4 &cleaned, const float4x4 &mat)
static float4x4 clean_obmat(const float4x4 &mat)
{
float4x4 cleaned;
const float fuzz = 1e-6f;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
@ -69,6 +70,7 @@ static void clean_obmat(float4x4 &cleaned, const float4x4 &mat)
cleaned.values[i][j] = f;
}
}
return cleaned;
}
/* `MeshesToIMeshInfo` keeps track of information used when combining a number
@ -92,7 +94,7 @@ class MeshesToIMeshInfo {
Array<Face *> mesh_to_imesh_face;
/* Transformation matrix to transform a coordinate in the corresponding
* Mesh to the local space of the first Mesh. */
Array<float4x4> to_obj0;
Array<float4x4> to_target_transform;
/* For each input mesh, how to remap the material slot numbers to
* the material slots in the first mesh. */
Array<const short *> material_remaps;
@ -242,6 +244,7 @@ const MEdge *MeshesToIMeshInfo::input_medge_for_orig_index(int orig_index,
static IMesh meshes_to_imesh(Span<const Mesh *> meshes,
Span<const float4x4 *> obmats,
Span<const short *> material_remaps,
const float4x4 &target_transform,
IMeshArena &arena,
MeshesToIMeshInfo *r_info)
{
@ -270,7 +273,7 @@ static IMesh meshes_to_imesh(Span<const Mesh *> meshes,
r_info->mesh_vert_offset = Array<int>(nmeshes);
r_info->mesh_edge_offset = Array<int>(nmeshes);
r_info->mesh_poly_offset = Array<int>(nmeshes);
r_info->to_obj0 = Array<float4x4>(nmeshes);
r_info->to_target_transform = Array<float4x4>(nmeshes);
r_info->material_remaps = Array<const short *>(nmeshes);
int v = 0;
int e = 0;
@ -283,19 +286,10 @@ static IMesh meshes_to_imesh(Span<const Mesh *> meshes,
Vector<int, estimated_max_facelen> face_edge_orig;
/* To convert the coordinates of objects 1, 2, etc. into the local space
* of object 0, we multiply each object's `obmat` by the inverse of
* object 0's `obmat`. Exact Boolean works better if these matrices
* are 'cleaned' -- see the comment for the `clean_obmat` function, above. */
float4x4 obj0_mat;
float4x4 inv_obj0_mat;
if (obmats[0] == nullptr) {
unit_m4(obj0_mat.values);
unit_m4(inv_obj0_mat.values);
}
else {
clean_obmat(obj0_mat, *obmats[0]);
invert_m4_m4(inv_obj0_mat.values, obj0_mat.values);
}
* of the target. We multiply each object's `obmat` by the inverse of the
* target matrix. Exact Boolean works better if these matrices are 'cleaned'
* -- see the comment for the `clean_obmat` function, above. */
const float4x4 inv_target_mat = clean_obmat(target_transform).inverted();
/* For each input `Mesh`, make `Vert`s and `Face`s for the corresponding
* `MVert`s and `MPoly`s, and keep track of the original indices (using the
@ -303,45 +297,41 @@ static IMesh meshes_to_imesh(Span<const Mesh *> meshes,
* When making `Face`s, we also put in the original indices for `MEdge`s that
* make up the `MPoly`s using the same scheme. */
for (int mi : meshes.index_range()) {
float4x4 objn_to_obj0_mat;
const Mesh *me = meshes[mi];
if (mi == 0) {
r_info->mesh_vert_offset[mi] = 0;
r_info->mesh_edge_offset[mi] = 0;
r_info->mesh_poly_offset[mi] = 0;
unit_m4(r_info->to_obj0[0].values);
r_info->material_remaps[0] = nullptr;
r_info->mesh_vert_offset[mi] = v;
r_info->mesh_edge_offset[mi] = e;
r_info->mesh_poly_offset[mi] = f;
/* Get matrix that transforms a coordinate in objects[mi]'s local space
* to the target space space.*/
const float4x4 objn_mat = (obmats[mi] == nullptr) ? float4x4::identity() :
clean_obmat(*obmats[mi]);
r_info->to_target_transform[mi] = inv_target_mat * objn_mat;
if (mi < material_remaps.size() && mi != 0) {
r_info->material_remaps[mi] = material_remaps[mi];
}
else {
r_info->mesh_vert_offset[mi] = v;
r_info->mesh_edge_offset[mi] = e;
r_info->mesh_poly_offset[mi] = f;
/* Get matrix that transforms a coordinate in objects[mi]'s local space
* to object[0]'s local space.*/
float4x4 objn_mat;
if (obmats[mi] == nullptr) {
unit_m4(objn_mat.values);
}
else {
clean_obmat(objn_mat, *obmats[mi]);
}
objn_to_obj0_mat = inv_obj0_mat * objn_mat;
r_info->to_obj0[mi] = objn_to_obj0_mat;
if (mi < material_remaps.size()) {
r_info->material_remaps[mi] = material_remaps[mi];
}
else {
r_info->material_remaps[mi] = nullptr;
r_info->material_remaps[mi] = nullptr;
}
/* Skip the matrix multiplication for each point when there is no transform for a mesh,
* for example when the first mesh is already in the target space. (Note the logic directly
* above, which uses an identity matrix with a null input transform). */
if (obmats[mi] == nullptr) {
for (const MVert &vert : Span(me->mvert, me->totvert)) {
const float3 co = float3(vert.co);
r_info->mesh_to_imesh_vert[v] = arena.add_or_find_vert(mpq3(co.x, co.y, co.z), v);
++v;
}
}
for (int vi = 0; vi < me->totvert; ++vi) {
float3 co = me->mvert[vi].co;
if (mi > 0) {
co = objn_to_obj0_mat * co;
else {
for (const MVert &vert : Span(me->mvert, me->totvert)) {
const float3 co = r_info->to_target_transform[mi] * float3(vert.co);
r_info->mesh_to_imesh_vert[v] = arena.add_or_find_vert(mpq3(co.x, co.y, co.z), v);
++v;
}
r_info->mesh_to_imesh_vert[v] = arena.add_or_find_vert(mpq3(co.x, co.y, co.z), v);
++v;
}
for (const MPoly &poly : Span(me->mpoly, me->totpoly)) {
int flen = poly.totloop;
face_vert.clear();
@ -596,7 +586,7 @@ static void copy_or_interp_loop_attributes(Mesh *dest_mesh,
cos_2d = (float(*)[2])BLI_array_alloca(cos_2d, orig_mp->totloop);
weights = Array<float>(orig_mp->totloop);
src_blocks_ofs = Array<const void *>(orig_mp->totloop);
get_poly2d_cos(orig_me, orig_mp, cos_2d, mim.to_obj0[orig_me_index], axis_mat);
get_poly2d_cos(orig_me, orig_mp, cos_2d, mim.to_target_transform[orig_me_index], axis_mat);
}
CustomData *target_cd = &dest_mesh->ldata;
for (int i = 0; i < mp->totloop; ++i) {
@ -778,17 +768,21 @@ static Mesh *imesh_to_mesh(IMesh *im, MeshesToIMeshInfo &mim)
return result;
}
#endif // WITH_GMP
/**
* Do Exact Boolean directly, without a round trip through #BMesh.
* The Mesh operands are in `meshes`, with corresponding transforms in in `obmats`.
*/
static Mesh *direct_mesh_boolean(Span<const Mesh *> meshes,
Span<const float4x4 *> obmats,
Span<const short *> material_remaps,
const bool use_self,
const bool hole_tolerant,
const BoolOpType boolean_mode)
Mesh *direct_mesh_boolean(Span<const Mesh *> meshes,
Span<const float4x4 *> obmats,
const float4x4 &target_transform,
Span<const short *> material_remaps,
const bool use_self,
const bool hole_tolerant,
const int boolean_mode)
{
#ifdef WITH_GMP
const int dbg_level = 0;
BLI_assert(meshes.size() == obmats.size());
const int meshes_len = meshes.size();
@ -800,7 +794,7 @@ static Mesh *direct_mesh_boolean(Span<const Mesh *> meshes,
}
MeshesToIMeshInfo mim;
IMeshArena arena;
IMesh m_in = meshes_to_imesh(meshes, obmats, material_remaps, arena, &mim);
IMesh m_in = meshes_to_imesh(meshes, obmats, material_remaps, target_transform, arena, &mim);
std::function<int(int)> shape_fn = [&mim](int f) {
for (int mi = 0; mi < mim.mesh_poly_offset.size() - 1; ++mi) {
if (f < mim.mesh_poly_offset[mi + 1]) {
@ -809,17 +803,27 @@ static Mesh *direct_mesh_boolean(Span<const Mesh *> meshes,
}
return static_cast<int>(mim.mesh_poly_offset.size()) - 1;
};
IMesh m_out = boolean_mesh(
m_in, boolean_mode, meshes_len, shape_fn, use_self, hole_tolerant, nullptr, &arena);
IMesh m_out = boolean_mesh(m_in,
static_cast<BoolOpType>(boolean_mode),
meshes_len,
shape_fn,
use_self,
hole_tolerant,
nullptr,
&arena);
if (dbg_level > 1) {
std::cout << m_out;
write_obj_mesh(m_out, "m_out");
}
return imesh_to_mesh(&m_out, mim);
#else // WITH_GMP
UNUSED_VARS(
meshes, obmats, material_remaps, target_transform, use_self, hole_tolerant, boolean_mode);
return nullptr;
#endif // WITH_GMP
}
#endif // WITH_GMP
} // namespace blender::meshintersect
extern "C" {
@ -835,6 +839,7 @@ extern "C" {
* for the pointers to be nullptr, meaning the transformation is the identity. */
Mesh *BKE_mesh_boolean(const Mesh **meshes,
const float (*obmats[])[4][4],
const float (*target_transform)[4][4],
const short **material_remaps,
const int meshes_len,
const bool use_self,
@ -842,25 +847,28 @@ Mesh *BKE_mesh_boolean(const Mesh **meshes,
const int boolean_mode)
{
const blender::float4x4 **transforms = (const blender::float4x4 **)obmats;
const blender::float4x4 &target_float4x4 = *(const blender::float4x4 *)target_transform;
return blender::meshintersect::direct_mesh_boolean(
blender::Span(meshes, meshes_len),
blender::Span(transforms, meshes_len),
target_float4x4,
blender::Span(material_remaps, material_remaps ? meshes_len : 0),
use_self,
hole_tolerant,
static_cast<blender::meshintersect::BoolOpType>(boolean_mode));
boolean_mode);
}
#else
Mesh *BKE_mesh_boolean(const Mesh **UNUSED(meshes),
const float (*obmats[])[4][4],
const float (*target_transform)[4][4],
const short **UNUSED(material_remaps),
const int UNUSED(meshes_len),
const bool UNUSED(use_self),
const bool UNUSED(hole_tolerant),
const int UNUSED(boolean_mode))
{
UNUSED_VARS(obmats);
UNUSED_VARS(obmats, target_transform);
return NULL;
}

2
source/blender/makesrna/intern/rna_nodetree.c
View File

@ -8785,7 +8785,7 @@ static void def_geo_boolean(StructRNA *srna)
RNA_def_property_enum_items(prop, rna_node_geometry_boolean_method_items);
RNA_def_property_enum_default(prop, GEO_NODE_BOOLEAN_INTERSECT);
RNA_def_property_ui_text(prop, "Operation", "");
RNA_def_property_update(prop, NC_NODE | NA_EDITED, "rna_Node_update");
RNA_def_property_update(prop, NC_NODE | NA_EDITED, "rna_Node_socket_update");
}
static void def_geo_triangulate(StructRNA *srna)

1
source/blender/modifiers/intern/MOD_boolean.c
View File

@ -694,6 +694,7 @@ static Mesh *exact_boolean_mesh(BooleanModifierData *bmd,
const bool hole_tolerant = (bmd->flag & eBooleanModifierFlag_HoleTolerant) != 0;
result = BKE_mesh_boolean((const Mesh **)meshes,
(const float(**)[4][4])obmats,
&ctx->object->obmat,
(const short **)material_remaps,
BLI_array_len(meshes),
use_self,

172
source/blender/nodes/geometry/nodes/node_geo_boolean.cc
View File

@ -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))
static void geo_node_boolean_update(bNodeTree *UNUSED(ntree), bNode *node)
{
return BM_elem_flag_test(f, BM_ELEM_DRAW) ? 1 : 0;
GeometryNodeBooleanOperation operation = (GeometryNodeBooleanOperation)node->custom1;
bNodeSocket *geometry_1_socket = (bNodeSocket *)node->inputs.first;
bNodeSocket *geometry_2_socket = geometry_1_socket->next;
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;
}
}
static Mesh *mesh_boolean_calc(const Mesh *mesh_a, const Mesh *mesh_b, int boolean_mode)
static void geo_node_boolean_init(bNodeTree *UNUSED(tree), 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);
/* Temp tag to test which side split faces are from. */
BM_elem_flag_enable(bm_face, BM_ELEM_DRAW);
i++;
if (i == i_faces_end) {
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;
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;
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();
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);
}
else {
params.set_output("Geometry", geometry_set_in_b);
}
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);
}
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);
/* 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);
}
params.set_output("Geometry", std::move(geometry_set_out));
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);
}
}
}
Mesh *result = blender::meshintersect::direct_mesh_boolean(
meshes, transforms, float4x4::identity(), {}, use_self, hole_tolerant, operation);
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);
}