diff options
| -rw-r--r-- | source/blender/blenlib/intern/mesh_boolean.cc | 82 | ||||
| -rw-r--r-- | source/blender/blenloader/intern/versioning_290.c | 27 | ||||
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_boolean.cc | 19 | ||||
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_boolean.h | 2 | ||||
| -rw-r--r-- | source/blender/editors/mesh/editmesh_intersect.c | 5 | ||||
| -rw-r--r-- | source/blender/editors/sculpt_paint/paint_mask.c | 2 | ||||
| -rw-r--r-- | source/blender/makesdna/DNA_modifier_types.h | 8 | ||||
| -rw-r--r-- | source/blender/makesrna/intern/rna_modifier.c | 34 | ||||
| -rw-r--r-- | source/blender/modifiers/intern/MOD_boolean.c | 660 |
9 files changed, 602 insertions, 237 deletions
diff --git a/source/blender/blenlib/intern/mesh_boolean.cc b/source/blender/blenlib/intern/mesh_boolean.cc index e92751efe72..a6ab30a3b26 100644 --- a/source/blender/blenlib/intern/mesh_boolean.cc +++ b/source/blender/blenlib/intern/mesh_boolean.cc @@ -2068,11 +2068,11 @@ static bool apply_bool_op(BoolOpType bool_optype, const Array<int> &winding) return true; } for (int i = 1; i < nw; ++i) { - if (winding[i] == 0) { - return true; + if (winding[i] == 1) { + return false; } } - return false; + return true; } default: return false; @@ -2398,8 +2398,7 @@ static IMesh gwn_boolean(const IMesh &tm, IMesh ans; Vector<Face *> out_faces; out_faces.reserve(tm.face_size()); - BLI_assert(nshapes == 2); /* TODO: generalize. */ - UNUSED_VARS_NDEBUG(nshapes); + Array<int> winding(nshapes, 0); for (int p : pinfo.index_range()) { const Patch &patch = pinfo.patch(p); /* For test triangle, choose one in the middle of patch list @@ -2421,40 +2420,41 @@ static IMesh gwn_boolean(const IMesh &tm, if (dbg_level > 0) { std::cout << "test point = " << test_point_db << "\n"; } - int other_shape = 1 - shape; - /* The point_is_inside_shape function has to approximate if the other - * shape is not PWN. For most operations, even a hint of being inside - * gives good results, but when shape is the cutter in a Difference - * operation, we want to be pretty sure that the point is inside other_shape. - * E.g., T75827. - */ - bool need_high_confidence = (op == BoolOpType::Difference) && (shape == 1); - bool inside = point_is_inside_shape( - tm, shape_fn, test_point_db, other_shape, need_high_confidence); - if (dbg_level > 0) { - std::cout << "test point is " << (inside ? "inside\n" : "outside\n"); - } - bool do_remove; - bool do_flip; - switch (op) { - case BoolOpType::Intersect: - do_remove = !inside; - do_flip = false; - break; - case BoolOpType::Union: - do_remove = inside; - do_flip = false; - break; - case BoolOpType::Difference: - do_remove = (shape == 0) ? inside : !inside; - do_flip = (shape == 1); - break; - default: - do_remove = false; - do_flip = false; - BLI_assert(false); + for (int other_shape = 0; other_shape < nshapes; ++other_shape) { + if (other_shape == shape) { + continue; + } + /* The point_is_inside_shape function has to approximate if the other + * shape is not PWN. For most operations, even a hint of being inside + * gives good results, but when shape is a cutter in a Difference + * operation, we want to be pretty sure that the point is inside other_shape. + * E.g., T75827. + */ + bool need_high_confidence = (op == BoolOpType::Difference) && (shape != 0); + bool inside = point_is_inside_shape( + tm, shape_fn, test_point_db, other_shape, need_high_confidence); + if (dbg_level > 0) { + std::cout << "test point is " << (inside ? "inside" : "outside") << " other_shape " + << other_shape << "\n"; + } + winding[other_shape] = inside; } + /* Find out the "in the output volume" flag for each of the cases of winding[shape] == 0 + * and winding[shape] == 1. If the flags are different, this patch should be in the output. + * Also, if this is a Difference and the shape isn't the first one, need to flip the normals. + */ + winding[shape] = 0; + bool in_output_volume_0 = apply_bool_op(op, winding); + winding[shape] = 1; + bool in_output_volume_1 = apply_bool_op(op, winding); + bool do_remove = in_output_volume_0 == in_output_volume_1; + bool do_flip = !do_remove && op == BoolOpType::Difference && shape != 0; if (dbg_level > 0) { + std::cout << "winding = "; + for (int i = 0; i < nshapes; ++i) { + std::cout << winding[i] << " "; + } + std::cout << "\niv0=" << in_output_volume_0 << ", iv1=" << in_output_volume_1 << "\n"; std::cout << "result for patch " << p << ": remove=" << do_remove << ", flip=" << do_flip << "\n"; } @@ -3270,13 +3270,7 @@ IMesh boolean_trimesh(IMesh &tm_in, if (tm_in.face_size() == 0) { return IMesh(tm_in); } - IMesh tm_si; - if (use_self) { - tm_si = trimesh_self_intersect(tm_in, arena); - } - else { - tm_si = trimesh_nary_intersect(tm_in, nshapes, shape_fn, use_self, arena); - } + IMesh tm_si = trimesh_nary_intersect(tm_in, nshapes, shape_fn, use_self, arena); if (dbg_level > 1) { write_obj_mesh(tm_si, "boolean_tm_si"); std::cout << "\nboolean_tm_input after intersection:\n" << tm_si; diff --git a/source/blender/blenloader/intern/versioning_290.c b/source/blender/blenloader/intern/versioning_290.c index b573fb28474..7805dbdcefa 100644 --- a/source/blender/blenloader/intern/versioning_290.c +++ b/source/blender/blenloader/intern/versioning_290.c @@ -526,19 +526,6 @@ void blo_do_versions_290(FileData *fd, Library *UNUSED(lib), Main *bmain) } } } - - /* Initialize solver for Boolean. */ - if (!DNA_struct_elem_find(fd->filesdna, "BooleanModifierData", "enum", "solver")) { - for (Object *object = bmain->objects.first; object != NULL; object = object->id.next) { - LISTBASE_FOREACH (ModifierData *, md, &object->modifiers) { - if (md->type == eModifierType_Boolean) { - BooleanModifierData *bmd = (BooleanModifierData *)md; - bmd->solver = eBooleanModifierSolver_Fast; - bmd->flag = 0; - } - } - } - } } for (Scene *scene = bmain->scenes.first; scene; scene = scene->id.next) { @@ -597,6 +584,20 @@ void blo_do_versions_290(FileData *fd, Library *UNUSED(lib), Main *bmain) } } } + + /* Solver and Collections for Boolean. */ + if (!DNA_struct_elem_find(fd->filesdna, "BooleanModifierData", "char", "solver")) { + for (Object *object = bmain->objects.first; object != NULL; object = object->id.next) { + LISTBASE_FOREACH (ModifierData *, md, &object->modifiers) { + if (md->type == eModifierType_Boolean) { + BooleanModifierData *bmd = (BooleanModifierData *)md; + bmd->solver = eBooleanModifierSolver_Fast; + bmd->flag = eBooleanModifierFlag_Object; + } + } + } + } + /* Keep this block, even when empty. */ } } diff --git a/source/blender/bmesh/tools/bmesh_boolean.cc b/source/blender/bmesh/tools/bmesh_boolean.cc index d2f73dd63ec..56585cb722e 100644 --- a/source/blender/bmesh/tools/bmesh_boolean.cc +++ b/source/blender/bmesh/tools/bmesh_boolean.cc @@ -194,6 +194,7 @@ static bool apply_mesh_output_to_bmesh(BMesh *bm, IMesh &m_out) /* Initially mark all existing faces as "don't keep", except hidden faces. * Also, save current #BMFace pointers as creating faces will disturb the table. */ Array<BMFace *> old_bmfs(bm->totface); + BM_mesh_elem_index_ensure(bm, BM_FACE); for (int f = 0; f < bm->totface; ++f) { BMFace *bmf = BM_face_at_index(bm, f); old_bmfs[f] = bmf; @@ -331,6 +332,7 @@ static bool bmesh_boolean(BMesh *bm, const int looptris_tot, int (*test_fn)(BMFace *f, void *user_data), void *user_data, + int nshapes, const bool use_self, const bool use_separate_all, const BoolOpType boolean_mode) @@ -339,10 +341,9 @@ static bool bmesh_boolean(BMesh *bm, IMesh m_triangulated; IMesh m_in = mesh_from_bm(bm, looptris, looptris_tot, &m_triangulated, &arena); std::function<int(int)> shape_fn; - int nshapes; if (use_self && boolean_mode == BoolOpType::None) { /* Unary knife operation. Want every face where test_fn doesn't return -1. */ - nshapes = 1; + BLI_assert(nshapes == 1); shape_fn = [bm, test_fn, user_data](int f) { BMFace *bmf = BM_face_at_index(bm, f); if (test_fn(bmf, user_data) != -1) { @@ -352,15 +353,11 @@ static bool bmesh_boolean(BMesh *bm, }; } else { - nshapes = 2; shape_fn = [bm, test_fn, user_data](int f) { BMFace *bmf = BM_face_at_index(bm, f); int test_val = test_fn(bmf, user_data); - if (test_val == 0) { - return 0; - } - if (test_val == 1) { - return 1; + if (test_val >= 0) { + return test_val; } return -1; }; @@ -403,6 +400,7 @@ bool BM_mesh_boolean(BMesh *bm, const int looptris_tot, int (*test_fn)(BMFace *f, void *user_data), void *user_data, + const int nshapes, const bool use_self, const int boolean_mode) { @@ -412,6 +410,7 @@ bool BM_mesh_boolean(BMesh *bm, looptris_tot, test_fn, user_data, + nshapes, use_self, false, static_cast<blender::meshintersect::BoolOpType>(boolean_mode)); @@ -430,6 +429,7 @@ bool BM_mesh_boolean_knife(BMesh *bm, const int looptris_tot, int (*test_fn)(BMFace *f, void *user_data), void *user_data, + const int nshapes, const bool use_self, const bool use_separate_all) { @@ -438,6 +438,7 @@ bool BM_mesh_boolean_knife(BMesh *bm, looptris_tot, test_fn, user_data, + nshapes, use_self, use_separate_all, blender::meshintersect::BoolOpType::None); @@ -448,6 +449,7 @@ bool BM_mesh_boolean(BMesh *UNUSED(bm), const int UNUSED(looptris_tot), int (*test_fn)(BMFace *, void *), void *UNUSED(user_data), + const int UNUSED(nshapes), const bool UNUSED(use_self), const int UNUSED(boolean_mode)) { @@ -468,6 +470,7 @@ bool BM_mesh_boolean_knife(BMesh *UNUSED(bm), const int UNUSED(looptris_tot), int (*test_fn)(BMFace *, void *), void *UNUSED(user_data), + const int UNUSED(nshapes), const bool UNUSED(use_self), const bool UNUSED(use_separate_all)) { diff --git a/source/blender/bmesh/tools/bmesh_boolean.h b/source/blender/bmesh/tools/bmesh_boolean.h index d1b4fb2509c..04b5205ec84 100644 --- a/source/blender/bmesh/tools/bmesh_boolean.h +++ b/source/blender/bmesh/tools/bmesh_boolean.h @@ -29,6 +29,7 @@ bool BM_mesh_boolean(BMesh *bm, const int looptris_tot, int (*test_fn)(BMFace *f, void *user_data), void *user_data, + const int nshapes, const bool use_self, const int boolean_mode); @@ -37,6 +38,7 @@ bool BM_mesh_boolean_knife(BMesh *bm, const int looptris_tot, int (*test_fn)(BMFace *f, void *user_data), void *user_data, + const int nshapes, const bool use_self, const bool use_separate_all); diff --git a/source/blender/editors/mesh/editmesh_intersect.c b/source/blender/editors/mesh/editmesh_intersect.c index 1b5e374b2a7..528ad57b9bf 100644 --- a/source/blender/editors/mesh/editmesh_intersect.c +++ b/source/blender/editors/mesh/editmesh_intersect.c @@ -204,8 +204,9 @@ static int edbm_intersect_exec(bContext *C, wmOperator *op) } if (exact) { + int nshapes = use_self ? 1 : 2; has_isect = BM_mesh_boolean_knife( - em->bm, em->looptris, em->tottri, test_fn, NULL, use_self, use_separate_all); + em->bm, em->looptris, em->tottri, test_fn, NULL, nshapes, use_self, use_separate_all); } else { has_isect = BM_mesh_intersect(em->bm, @@ -373,7 +374,7 @@ static int edbm_intersect_boolean_exec(bContext *C, wmOperator *op) if (use_exact) { has_isect = BM_mesh_boolean( - em->bm, em->looptris, em->tottri, test_fn, NULL, use_self, boolean_operation); + em->bm, em->looptris, em->tottri, test_fn, NULL, 2, use_self, boolean_operation); } else { has_isect = BM_mesh_intersect(em->bm, diff --git a/source/blender/editors/sculpt_paint/paint_mask.c b/source/blender/editors/sculpt_paint/paint_mask.c index 70f8ef89e9a..c9fdf3c238d 100644 --- a/source/blender/editors/sculpt_paint/paint_mask.c +++ b/source/blender/editors/sculpt_paint/paint_mask.c @@ -1022,7 +1022,7 @@ static void sculpt_gesture_apply_trim(SculptGestureContext *sgcontext) break; } - BM_mesh_boolean(bm, looptris, tottri, bm_face_isect_pair, NULL, false, boolean_mode); + BM_mesh_boolean(bm, looptris, tottri, bm_face_isect_pair, NULL, 2, false, boolean_mode); Mesh *result = BKE_mesh_from_bmesh_for_eval_nomain(bm, NULL, sculpt_mesh); BM_mesh_free(bm); diff --git a/source/blender/makesdna/DNA_modifier_types.h b/source/blender/makesdna/DNA_modifier_types.h index a9f1d5bcfc4..9a5b5b8c2ca 100644 --- a/source/blender/makesdna/DNA_modifier_types.h +++ b/source/blender/makesdna/DNA_modifier_types.h @@ -861,26 +861,32 @@ typedef struct BooleanModifierData { ModifierData modifier; struct Object *object; + struct Collection *collection; + float double_threshold; char operation; char solver; char flag; char bm_flag; - float double_threshold; } BooleanModifierData; +/* BooleanModifierData->operation */ typedef enum { eBooleanModifierOp_Intersect = 0, eBooleanModifierOp_Union = 1, eBooleanModifierOp_Difference = 2, } BooleanModifierOp; +/* BooleanModifierData->solver */ typedef enum { eBooleanModifierSolver_Fast = 0, eBooleanModifierSolver_Exact = 1, } BooleanModifierSolver; +/* BooleanModifierData->flag */ enum { eBooleanModifierFlag_Self = (1 << 0), + eBooleanModifierFlag_Object = (1 << 1), + eBooleanModifierFlag_Collection = (1 << 2), }; /* bm_flag only used when G_DEBUG. */ diff --git a/source/blender/makesrna/intern/rna_modifier.c b/source/blender/makesrna/intern/rna_modifier.c index 1bf14f86189..2463f3c409f 100644 --- a/source/blender/makesrna/intern/rna_modifier.c +++ b/source/blender/makesrna/intern/rna_modifier.c @@ -2804,18 +2804,32 @@ static void rna_def_modifier_boolean(BlenderRNA *brna) StructRNA *srna; PropertyRNA *prop; + static const EnumPropertyItem prop_operand_items[] = { + {eBooleanModifierFlag_Object, + "OBJECT", + 0, + "Object", + "Use a mesh object as the operand for the Boolean operation"}, + {eBooleanModifierFlag_Collection, + "COLLECTION", + 0, + "Collection", + "Use a collection of mesh objects as the operand for the Boolean operation"}, + {0, NULL, 0, NULL, NULL}, + }; + static const EnumPropertyItem prop_operation_items[] = { {eBooleanModifierOp_Intersect, "INTERSECT", 0, "Intersect", - "Keep the part of the mesh that intersects with the other selected object"}, - {eBooleanModifierOp_Union, "UNION", 0, "Union", "Combine two meshes in an additive way"}, + "Keep the part of the mesh that is common between all operands"}, + {eBooleanModifierOp_Union, "UNION", 0, "Union", "Combine meshes in an additive way"}, {eBooleanModifierOp_Difference, "DIFFERENCE", 0, "Difference", - "Combine two meshes in a subtractive way"}, + "Combine meshes in a subtractive way"}, {0, NULL, 0, NULL, NULL}, }; @@ -2843,12 +2857,26 @@ static void rna_def_modifier_boolean(BlenderRNA *brna) RNA_def_property_flag(prop, PROP_EDITABLE | PROP_ID_SELF_CHECK); RNA_def_property_update(prop, 0, "rna_Modifier_dependency_update"); + prop = RNA_def_property(srna, "collection", PROP_POINTER, PROP_NONE); + RNA_def_property_pointer_sdna(prop, NULL, "collection"); + RNA_def_property_struct_type(prop, "Collection"); + RNA_def_property_flag(prop, PROP_EDITABLE | PROP_ID_REFCOUNT); + RNA_def_property_ui_text( + prop, "Collection", "Use mesh objects in this collection for Boolean operation"); + RNA_def_property_update(prop, 0, "rna_Modifier_dependency_update"); + prop = RNA_def_property(srna, "operation", PROP_ENUM, PROP_NONE); RNA_def_property_enum_items(prop, prop_operation_items); RNA_def_property_enum_default(prop, eBooleanModifierOp_Difference); RNA_def_property_ui_text(prop, "Operation", ""); RNA_def_property_update(prop, 0, "rna_Modifier_update"); + prop = RNA_def_property(srna, "operand_type", PROP_ENUM, PROP_NONE); + RNA_def_property_enum_bitflag_sdna(prop, NULL, "flag"); + RNA_def_property_enum_items(prop, prop_operand_items); + RNA_def_property_ui_text(prop, "Operand Type", ""); + RNA_def_property_update(prop, 0, "rna_Modifier_update"); + prop = RNA_def_property(srna, "double_threshold", PROP_FLOAT, PROP_DISTANCE); RNA_def_property_float_sdna(prop, NULL, "double_threshold"); RNA_def_property_range(prop, 0, 1.0f); diff --git a/source/blender/modifiers/intern/MOD_boolean.c b/source/blender/modifiers/intern/MOD_boolean.c index bef7d5d8e4f..cd552d4e1ad 100644 --- a/source/blender/modifiers/intern/MOD_boolean.c +++ b/source/blender/modifiers/intern/MOD_boolean.c @@ -28,16 +28,20 @@ #include "BLI_utildefines.h" #include "BLI_alloca.h" +#include "BLI_array.h" #include "BLI_math_geom.h" #include "BLI_math_matrix.h" #include "BLT_translation.h" +#include "DNA_collection_types.h" #include "DNA_mesh_types.h" #include "DNA_meshdata_types.h" #include "DNA_object_types.h" +#include "DNA_scene_types.h" #include "DNA_screen_types.h" +#include "BKE_collection.h" #include "BKE_context.h" #include "BKE_global.h" /* only to check G.debug */ #include "BKE_lib_id.h" @@ -65,6 +69,7 @@ #include "tools/bmesh_boolean.h" #include "tools/bmesh_intersect.h" +// #define DEBUG_TIME #ifdef DEBUG_TIME # include "PIL_time.h" # include "PIL_time_utildefines.h" @@ -77,7 +82,7 @@ static void initData(ModifierData *md) bmd->double_threshold = 1e-6f; bmd->operation = eBooleanModifierOp_Difference; bmd->solver = eBooleanModifierSolver_Exact; - bmd->flag = 0; + bmd->flag = eBooleanModifierFlag_Object; } static bool isDisabled(const struct Scene *UNUSED(scene), @@ -85,13 +90,15 @@ static bool isDisabled(const struct Scene *UNUSED(scene), bool UNUSED(useRenderParams)) { BooleanModifierData *bmd = (BooleanModifierData *)md; + Collection *col = bmd->collection; - /* The object type check is only needed here in case we have a placeholder - * object assigned (because the library containing the mesh is missing). - * - * In other cases it should be impossible to have a type mismatch. - */ - return !bmd->object || bmd->object->type != OB_MESH; + if (bmd->flag & eBooleanModifierFlag_Object) { + return !bmd->object || bmd->object->type != OB_MESH; + } + if (bmd->flag & eBooleanModifierFlag_Collection) { + return !col; + } + return false; } static void foreachObjectLink(ModifierData *md, Object *ob, ObjectWalkFunc walk, void *userData) @@ -101,23 +108,45 @@ static void foreachObjectLink(ModifierData *md, Object *ob, ObjectWalkFunc walk, walk(userData, ob, &bmd->object, IDWALK_CB_NOP); } +static void foreachIDLink(ModifierData *md, Object *ob, IDWalkFunc walk, void *userData) +{ + BooleanModifierData *bmd = (BooleanModifierData *)md; + + walk(userData, ob, (ID **)&bmd->collection, IDWALK_CB_NOP); + + /* Needed for the object operand to work. */ + foreachObjectLink(md, ob, (ObjectWalkFunc)walk, userData); +} + static void updateDepsgraph(ModifierData *md, const ModifierUpdateDepsgraphContext *ctx) { BooleanModifierData *bmd = (BooleanModifierData *)md; - if (bmd->object != NULL) { + if ((bmd->flag & eBooleanModifierFlag_Object) && bmd->object != NULL) { DEG_add_object_relation(ctx->node, bmd->object, DEG_OB_COMP_TRANSFORM, "Boolean Modifier"); DEG_add_object_relation(ctx->node, bmd->object, DEG_OB_COMP_GEOMETRY, "Boolean Modifier"); } + + Collection *col = bmd->collection; + + if ((bmd->flag & eBooleanModifierFlag_Collection) && col != NULL) { + FOREACH_COLLECTION_OBJECT_RECURSIVE_BEGIN (col, operand_ob) { + if (operand_ob->type == OB_MESH && operand_ob != ctx->object) { + DEG_add_object_relation(ctx->node, operand_ob, DEG_OB_COMP_TRANSFORM, "Boolean Modifier"); + DEG_add_object_relation(ctx->node, operand_ob, DEG_OB_COMP_GEOMETRY, "Boolean Modifier"); + } + } + FOREACH_COLLECTION_OBJECT_RECURSIVE_END; + } /* We need own transformation as well. */ DEG_add_modifier_to_transform_relation(ctx->node, "Boolean Modifier"); } static Mesh *get_quick_mesh( - Object *ob_self, Mesh *mesh_self, Object *ob_other, Mesh *mesh_other, int operation) + Object *ob_self, Mesh *mesh_self, Object *ob_operand_ob, Mesh *mesh_operand_ob, int operation) { Mesh *result = NULL; - if (mesh_self->totpoly == 0 || mesh_other->totpoly == 0) { + if (mesh_self->totpoly == 0 || mesh_operand_ob->totpoly == 0) { switch (operation) { case eBooleanModifierOp_Intersect: result = BKE_mesh_new_nomain(0, 0, 0, 0, 0); @@ -128,13 +157,13 @@ static Mesh *get_quick_mesh( result = mesh_self; } else { - BKE_id_copy_ex(NULL, &mesh_other->id, (ID **)&result, LIB_ID_COPY_LOCALIZE); + BKE_id_copy_ex(NULL, &mesh_operand_ob->id, (ID **)&result, LIB_ID_COPY_LOCALIZE); float imat[4][4]; float omat[4][4]; invert_m4_m4(imat, ob_self->obmat); - mul_m4_m4m4(omat, imat, ob_other->obmat); + mul_m4_m4m4(omat, imat, ob_operand_ob->obmat); const int mverts_len = result->totvert; MVert *mv = result->mvert; @@ -168,208 +197,496 @@ static int bm_face_isect_pair(BMFace *f, void *UNUSED(user_data)) return BM_elem_flag_test(f, BM_FACE_TAG) ? 1 : 0; } -static Mesh *modifyMesh(ModifierData *md, const ModifierEvalContext *ctx, Mesh *mesh) +static bool BMD_error_messages(ModifierData *md, Collection *col) { BooleanModifierData *bmd = (BooleanModifierData *)md; - Mesh *result = mesh; - Mesh *mesh_other; + bool error_returns_result = false; + + const bool operand_collection = (bmd->flag & eBooleanModifierFlag_Collection) != 0; + const bool use_exact = bmd->solver == eBooleanModifierSolver_Exact; + const bool operation_intersect = bmd->operation == eBooleanModifierOp_Intersect; - if (bmd->object == NULL) { - return result; +#ifndef WITH_GMP + /* If compiled without GMP, return a error. */ + if (use_exact) { + BKE_modifier_set_error(md, "Compiled without GMP, using fast solver"); + error_returns_result = false; } +#endif - Object *other = bmd->object; - mesh_other = BKE_modifier_get_evaluated_mesh_from_evaluated_object(other, false); - if (mesh_other) { - Object *object = ctx->object; + /* If intersect is selected using fast solver, return a error. */ + if (operand_collection && operation_intersect && !use_exact) { + BKE_modifier_set_error(md, "Cannot execute, intersect only available using exact solver"); + error_returns_result = true; + } - /* XXX This is utterly non-optimal, we may go from a bmesh to a mesh back to a bmesh! - * But for 2.90 better not try to be smart here. */ - BKE_mesh_wrapper_ensure_mdata(mesh_other); + /* If the selected collection is empty and using fast solver, return a error. */ + if (operand_collection) { + if (!use_exact && BKE_collection_is_empty(col)) { + BKE_modifier_set_error(md, "Cannot execute, fast solver and empty collection"); + error_returns_result = true; + } - /* when one of objects is empty (has got no faces) we could speed up - * calculation a bit returning one of objects' derived meshes (or empty one) - * Returning mesh is depended on modifiers operation (sergey) */ - result = get_quick_mesh(object, mesh, other, mesh_other, bmd->operation); + /* If the selected collection contain non mesh objects, return a error. */ + if (col) { + FOREACH_COLLECTION_OBJECT_RECURSIVE_BEGIN (col, operand_ob) { + if (operand_ob->type != OB_MESH) { + BKE_modifier_set_error( + md, "Cannot execute, the selected collection contains non mesh objects"); + error_returns_result = true; + } + } + FOREACH_COLLECTION_OBJECT_RECURSIVE_END; + } + } - if (result == NULL) { - const bool is_flip = (is_negative_m4(object->obmat) != is_negative_m4(other->obmat)); + return error_returns_result; +} - BMesh *bm; - const BMAllocTemplate allocsize = BMALLOC_TEMPLATE_FROM_ME(mesh, mesh_other); +static BMesh *BMD_mesh_bm_create( + Mesh *mesh, Object *object, Mesh *mesh_operand_ob, Object *operand_ob, bool *r_is_flip) +{ + BMesh *bm; -#ifdef DEBUG_TIME - TIMEIT_START(boolean_bmesh); -#endif - bm = BM_mesh_create(&allocsize, - &((struct BMeshCreateParams){ - .use_toolflags = false, - })); + *r_is_flip = (is_negative_m4(object->obmat) != is_negative_m4(operand_ob->obmat)); - BM_mesh_bm_from_me(bm, - mesh_other, - &((struct BMeshFromMeshParams){ - .calc_face_normal = true, - })); + const BMAllocTemplate allocsize = BMALLOC_TEMPLATE_FROM_ME(mesh, mesh_operand_ob); - if (UNLIKELY(is_flip)) { - const int cd_loop_mdisp_offset = CustomData_get_offset(&bm->ldata, CD_MDISPS); - BMIter iter; - BMFace *efa; - BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) { - BM_face_normal_flip_ex(bm, efa, cd_loop_mdisp_offset, true); - } - } + bm = BM_mesh_create(&allocsize, + &((struct BMeshCreateParams){ + .use_toolflags = false, + })); - BM_mesh_bm_from_me(bm, - mesh, - &((struct BMeshFromMeshParams){ - .calc_face_normal = true, - })); + BM_mesh_bm_from_me(bm, + mesh_operand_ob, + &((struct BMeshFromMeshParams){ + .calc_face_normal = true, + })); - /* main bmesh intersection setup */ - { - /* create tessface & intersect */ - const int looptris_tot = poly_to_tri_count(bm->totface, bm->totloop); - int tottri; - BMLoop *(*looptris)[3]; + if (UNLIKELY(*r_is_flip)) { + const int cd_loop_mdisp_offset = CustomData_get_offset(&bm->ldata, CD_MDISPS); + BMIter iter; + BMFace *efa; + BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) { + BM_face_normal_flip_ex(bm, efa, cd_loop_mdisp_offset, true); + } + } - looptris = MEM_malloc_arrayN(looptris_tot, sizeof(*looptris), __func__); + BM_mesh_bm_from_me(bm, + mesh, + &((struct BMeshFromMeshParams){ + .calc_face_normal = true, + })); - BM_mesh_calc_tessellation_beauty(bm, looptris, &tottri); + return bm; +} - /* postpone this until after tessellating - * so we can use the original normals before the vertex are moved */ - { - BMIter iter; - int i; - const int i_verts_end = mesh_other->totvert; - const int i_faces_end = mesh_other->totpoly; +static void BMD_mesh_intersection(BMesh *bm, + ModifierData *md, + const ModifierEvalContext *ctx, + Mesh *mesh_operand_ob, + Object *object, + Object *operand_ob, + bool is_flip) +{ + BooleanModifierData *bmd = (BooleanModifierData *)md; - float imat[4][4]; - float omat[4][4]; + /* main bmesh intersection setup */ + /* create tessface & intersect */ + const int looptris_tot = poly_to_tri_count(bm->totface, bm->totloop); + int tottri; + BMLoop *(*looptris)[3]; - invert_m4_m4(imat, object->obmat); - mul_m4_m4m4(omat, imat, other->obmat); + looptris = MEM_malloc_arrayN(looptris_tot, sizeof(*looptris), __func__); - BMVert *eve; - i = 0; - BM_ITER_MESH (eve, &iter, bm, BM_VERTS_OF_MESH) { - mul_m4_v3(omat, eve->co); - if (++i == i_verts_end) { - break; - } - } + BM_mesh_calc_tessellation_beauty(bm, looptris, &tottri); - /* we need face normals because of 'BM_face_split_edgenet' - * we could calculate on the fly too (before calling split). */ - { - float nmat[3][3]; - copy_m3_m4(nmat, omat); - invert_m3(nmat); + /* postpone this until after tessellating + * so we can use the original normals before the vertex are moved */ + { + BMIter iter; + int i; + const int i_verts_end = mesh_operand_ob->totvert; + const int i_faces_end = mesh_operand_ob->totpoly; - if (UNLIKELY(is_flip)) { - negate_m3(nmat); - } + float imat[4][4]; + float omat[4][4]; - const short ob_src_totcol = other->totcol; - short *material_remap = BLI_array_alloca(material_remap, - ob_src_totcol ? ob_src_totcol : 1); + invert_m4_m4(imat, object->obmat); + mul_m4_m4m4(omat, imat, operand_ob->obmat); - /* Using original (not evaluated) object here since we are writing to it. */ - /* XXX Pretty sure comment above is fully wrong now with CoW & co ? */ - BKE_object_material_remap_calc(ctx->object, other, material_remap); + BMVert *eve; + i = 0; + BM_ITER_MESH (eve, &iter, bm, BM_VERTS_OF_MESH) { + mul_m4_v3(omat, eve->co); + if (++i == i_verts_end) { + break; + } + } - BMFace *efa; - i = 0; - BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) { - mul_transposed_m3_v3(nmat, efa->no); - normalize_v3(efa->no); + /* we need face normals because of 'BM_face_split_edgenet' + * we could calculate on the fly too (before calling split). */ + { + float nmat[3][3]; + copy_m3_m4(nmat, omat); + invert_m3(nmat); - /* Temp tag to test which side split faces are from. */ - BM_elem_flag_enable(efa, BM_FACE_TAG); + if (UNLIKELY(is_flip)) { + negate_m3(nmat); + } - /* remap material */ - if (LIKELY(efa->mat_nr < ob_src_totcol)) { - efa->mat_nr = material_remap[efa->mat_nr]; - } + const short ob_src_totcol = operand_ob->totcol; + short *material_remap = BLI_array_alloca(material_remap, ob_src_totcol ? ob_src_totcol : 1); - if (++i == i_faces_end) { - break; - } - } - } - } + /* Using original (not evaluated) object here since we are writing to it. */ + /* XXX Pretty sure comment above is fully wrong now with CoW & co ? */ + BKE_object_material_remap_calc(ctx->object, operand_ob, material_remap); - /* not needed, but normals for 'dm' will be invalid, - * currently this is ok for 'BM_mesh_intersect' */ - // BM_mesh_normals_update(bm); + BMFace *efa; + i = 0; + BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) { + mul_transposed_m3_v3(nmat, efa->no); + normalize_v3(efa->no); - bool use_separate = false; - bool use_dissolve = true; - bool use_island_connect = true; + /* Temp tag to test which side split faces are from. */ + BM_elem_flag_enable(efa, BM_FACE_TAG); - /* change for testing */ - if (G.debug & G_DEBUG) { - use_separate = (bmd->bm_flag & eBooleanModifierBMeshFlag_BMesh_Separate) != 0; - use_dissolve = (bmd->bm_flag & eBooleanModifierBMeshFlag_BMesh_NoDissolve) == 0; - use_island_connect = (bmd->bm_flag & eBooleanModifierBMeshFlag_BMesh_NoConnectRegions) == - 0; + /* remap material */ + if (LIKELY(efa->mat_nr < ob_src_totcol)) { + efa->mat_nr = material_remap[efa->mat_nr]; } + if (++i == i_faces_end) { + break; + } + } + } + } + + /* not needed, but normals for 'dm' will be invalid, + * currently this is ok for 'BM_mesh_intersect' */ + // BM_mesh_normals_update(bm); + + bool use_separate = false; + bool use_dissolve = true; + bool use_island_connect = true; + + /* change for testing */ + if (G.debug & G_DEBUG) { + use_separate = (bmd->bm_flag & eBooleanModifierBMeshFlag_BMesh_Separate) != 0; + use_dissolve = (bmd->bm_flag & eBooleanModifierBMeshFlag_BMesh_NoDissolve) == 0; + use_island_connect = (bmd->bm_flag & eBooleanModifierBMeshFlag_BMesh_NoConnectRegions) == 0; + } + #ifdef WITH_GMP - const bool use_exact = bmd->solver == eBooleanModifierSolver_Exact; - const bool use_self = (bmd->flag & eBooleanModifierFlag_Self) != 0; + const bool use_exact = bmd->solver == eBooleanModifierSolver_Exact; + const bool use_self = (bmd->flag & eBooleanModifierFlag_Self) != 0; #else - if (bmd->solver == eBooleanModifierSolver_Exact) { - BKE_modifier_set_error(md, "Compiled without GMP, using fast solver"); - } - const bool use_exact = false; - const bool use_self = false; + const bool use_exact = false; + const bool use_self = false; #endif - if (use_exact) { - BM_mesh_boolean( - bm, looptris, tottri, bm_face_isect_pair, NULL, use_self, bmd->operation); - } - else { - BM_mesh_intersect(bm, - looptris, - tottri, - bm_face_isect_pair, - NULL, - false, - use_separate, - use_dissolve, - use_island_connect, - false, - false, - bmd->operation, - bmd->double_threshold); + if (use_exact) { + BM_mesh_boolean(bm, looptris, tottri, bm_face_isect_pair, NULL, 2, use_self, bmd->operation); + } + else { + BM_mesh_intersect(bm, + looptris, + tottri, + bm_face_isect_pair, + NULL, + false, + use_separate, + use_dissolve, + use_island_connect, + false, + false, + bmd->operation, + bmd->double_threshold); + } + MEM_freeN(looptris); +} + +static int bm_face_isect_nary(BMFace *f, void *user_data) +{ + int *shape = (int *)user_data; + return shape[BM_elem_index_get(f)]; +} + +/* The Exact solver can do all operands of a collection at once. */ +static Mesh *collection_boolean_exact(BooleanModifierData *bmd, + const ModifierEvalContext *ctx, + Mesh *mesh) +{ + int i; + Mesh *result = mesh; + Collection *col = bmd->collection; + int num_shapes = 1; + Mesh **meshes = NULL; + Object **objects = NULL; + BLI_array_declare(meshes); + BLI_array_declare(objects); + BMAllocTemplate bat; + bat.totvert = mesh->totvert; + bat.totedge = mesh->totedge; + bat.totloop = mesh->totloop; + bat.totface = mesh->totpoly; + BLI_array_append(meshes, mesh); + BLI_array_append(objects, ctx->object); + Mesh *col_mesh; + FOREACH_COLLECTION_OBJECT_RECURSIVE_BEGIN (col, ob) { + if (ob->type == OB_MESH && ob != ctx->object) { + col_mesh = BKE_modifier_get_evaluated_mesh_from_evaluated_object(ob, false); + /* XXX This is utterly non-optimal, we may go from a bmesh to a mesh back to a bmesh! + * But for 2.90 better not try to be smart here. */ + BKE_mesh_wrapper_ensure_mdata(col_mesh); + BLI_array_append(meshes, col_mesh); + BLI_array_append(objects, ob); + bat.totvert += col_mesh->totvert; + bat.totedge += col_mesh->totedge; + bat.totloop += col_mesh->totloop; + bat.totface += col_mesh->totpoly; + ++num_shapes; + } + } + FOREACH_COLLECTION_OBJECT_RECURSIVE_END; + int *shape_face_end = MEM_mallocN(num_shapes * sizeof(int), __func__); + int *shape_vert_end = MEM_mallocN(num_shapes * sizeof(int), __func__); + bool is_neg_mat0 = is_negative_m4(ctx->object->obmat); + BMesh *bm = BM_mesh_create(&bat, + &((struct BMeshCreateParams){ + .use_toolflags = false, + })); + for (i = 0; i < num_shapes; i++) { + Mesh *me = meshes[i]; + Object *ob = objects[i]; + /* Need normals for triangulation. */ + BM_mesh_bm_from_me(bm, + me, + &((struct BMeshFromMeshParams){ + .calc_face_normal = true, + })); + shape_face_end[i] = me->totpoly + (i == 0 ? 0 : shape_face_end[i - 1]); + shape_vert_end[i] = me->totvert + (i == 0 ? 0 : shape_vert_end[i - 1]); + if (i > 0) { + bool is_flip = (is_neg_mat0 != is_negative_m4(ob->obmat)); + if (UNLIKELY(is_flip)) { + const int cd_loop_mdisp_offset = CustomData_get_offset(&bm->ldata, CD_MDISPS); + BMIter iter; + BMFace *efa; + BM_mesh_elem_index_ensure(bm, BM_FACE); + BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) { + if (BM_elem_index_get(efa) >= shape_face_end[i - 1]) { + BM_face_normal_flip_ex(bm, efa, cd_loop_mdisp_offset, true); + } } + } + } + } - MEM_freeN(looptris); + /* Triangulate the mesh. */ + const int looptris_tot = poly_to_tri_count(bm->totface, bm->totloop); + int tottri; + BMLoop *(*looptris)[3]; + looptris = MEM_malloc_arrayN(looptris_tot, sizeof(*looptris), __func__); + BM_mesh_calc_tessellation_beauty(bm, looptris, &tottri); + + /* Move the vertices of all but the first shape into transformation space of first mesh. + * Do this after tesselation so don't need to recalculate normals. + * The Exact solver doesn't need normals on the input faces. */ + float imat[4][4]; + float omat[4][4]; + invert_m4_m4(imat, ctx->object->obmat); + int curshape = 0; + int curshape_vert_end = shape_vert_end[0]; + BMVert *eve; + BMIter iter; + i = 0; + BM_ITER_MESH (eve, &iter, bm, BM_VERTS_OF_MESH) { + if (i == curshape_vert_end) { + curshape++; + curshape_vert_end = shape_vert_end[curshape]; + mul_m4_m4m4(omat, imat, objects[curshape]->obmat); + } + if (curshape > 0) { + mul_m4_v3(omat, eve->co); + } + i++; + } + + /* Remap the materials. Fill a shape array for test function. Calculate normals. */ + int *shape = MEM_mallocN(bm->totface * sizeof(int), __func__); + curshape = 0; + int curshape_face_end = shape_face_end[0]; + int curshape_ncol = ctx->object->totcol; + short *material_remap = NULL; + BMFace *efa; + i = 0; + BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) { + if (i == curshape_face_end) { + curshape++; + curshape_face_end = shape_face_end[curshape]; + if (material_remap != NULL) { + MEM_freeN(material_remap); } + curshape_ncol = objects[curshape]->totcol; + material_remap = MEM_mallocN(curshape_ncol ? curshape_ncol : 1, __func__); + BKE_object_material_remap_calc(ctx->object, objects[curshape], material_remap); + } + shape[i] = curshape; + if (curshape > 0) { + /* Normals for other shapes changed because vertex positions changed. + * Boolean doesn't need these, but post-boolean code (interpolation) does. */ + BM_face_normal_update(efa); + if (LIKELY(efa->mat_nr < curshape_ncol)) { + efa->mat_nr = material_remap[efa->mat_nr]; + } + } + i++; + } - result = BKE_mesh_from_bmesh_for_eval_nomain(bm, NULL, mesh); + BM_mesh_elem_index_ensure(bm, BM_FACE); + BM_mesh_boolean( + bm, looptris, tottri, bm_face_isect_nary, shape, num_shapes, true, bmd->operation); - BM_mesh_free(bm); + result = BKE_mesh_from_bmesh_for_eval_nomain(bm, NULL, mesh); + BM_mesh_free(bm); + result->runtime.cd_dirty_vert |= CD_MASK_NORMAL; - result->runtime.cd_dirty_vert |= CD_MASK_NORMAL; + MEM_freeN(shape); + MEM_freeN(shape_face_end); + MEM_freeN(shape_vert_end); + MEM_freeN(looptris); + if (material_remap != NULL) { + MEM_freeN(material_remap); + } + BLI_array_free(meshes); + BLI_array_free(objects); + return result; +} + +static Mesh *modifyMesh(ModifierData *md, const ModifierEvalContext *ctx, Mesh *mesh) +{ + BooleanModifierData *bmd = (BooleanModifierData *)md; + Object *object = ctx->object; + Mesh *result = mesh; + Mesh *mesh_operand_ob; + BMesh *bm; + Collection *col = bmd->collection; + + bool is_flip = false; + const bool confirm_return = true; +#ifdef WITH_GMP + const bool use_exact = bmd->solver == eBooleanModifierSolver_Exact; +#else + const bool use_exact = false; +#endif #ifdef DEBUG_TIME - TIMEIT_END(boolean_bmesh); + TIMEIT_START(boolean_bmesh); #endif + + if (bmd->flag & eBooleanModifierFlag_Object) { + if (bmd->object == NULL) { + return result; } - /* if new mesh returned, return it; otherwise there was - * an error, so delete the modifier object */ - if (result == NULL) { - BKE_modifier_set_error(md, "Cannot execute boolean operation"); + BMD_error_messages(md, NULL); + + Object *operand_ob = bmd->object; + + mesh_operand_ob = BKE_modifier_get_evaluated_mesh_from_evaluated_object(operand_ob, false); + + if (mesh_operand_ob) { + /* XXX This is utterly non-optimal, we may go from a bmesh to a mesh back to a bmesh! + * But for 2.90 better not try to be smart here. */ + BKE_mesh_wrapper_ensure_mdata(mesh_operand_ob); + /* when one of objects is empty (has got no faces) we could speed up + * calculation a bit returning one of objects' derived meshes (or empty one) + * Returning mesh is depended on modifiers operation (sergey) */ + result = get_quick_mesh(object, mesh, operand_ob, mesh_operand_ob, bmd->operation); + + if (result == NULL) { + bm = BMD_mesh_bm_create(mesh, object, mesh_operand_ob, operand_ob, &is_flip); + + BMD_mesh_intersection(bm, md, ctx, mesh_operand_ob, object, operand_ob, is_flip); + + result = BKE_mesh_from_bmesh_for_eval_nomain(bm, NULL, mesh); + BM_mesh_free(bm); + result->runtime.cd_dirty_vert |= CD_MASK_NORMAL; + } + + /* if new mesh returned, return it; otherwise there was + * an error, so delete the modifier object */ + if (result == NULL) { + BKE_modifier_set_error(md, "Cannot execute boolean operation"); + } } } + else { + if (col == NULL && !use_exact) { + return result; + } + + /* Return result for certain errors. */ + if (BMD_error_messages(md, col) == confirm_return) { + return result; + } + + if (use_exact) { + result = collection_boolean_exact(bmd, ctx, mesh); + } + else { + FOREACH_COLLECTION_OBJECT_RECURSIVE_BEGIN (col, operand_ob) { + if (operand_ob->type == OB_MESH && operand_ob != ctx->object) { + + mesh_operand_ob = BKE_modifier_get_evaluated_mesh_from_evaluated_object(operand_ob, + false); + + if (mesh_operand_ob) { + /* XXX This is utterly non-optimal, we may go from a bmesh to a mesh back to a bmesh! + * But for 2.90 better not try to be smart here. */ + BKE_mesh_wrapper_ensure_mdata(mesh_operand_ob); + /* when one of objects is empty (has got no faces) we could speed up + * calculation a bit returning one of objects' derived meshes (or empty one) + * Returning mesh is depended on modifiers operation (sergey) */ + result = get_quick_mesh(object, mesh, operand_ob, mesh_operand_ob, bmd->operation); + + if (result == NULL) { + bm = BMD_mesh_bm_create(mesh, object, mesh_operand_ob, operand_ob, &is_flip); + + BMD_mesh_intersection(bm, md, ctx, mesh_operand_ob, object, operand_ob, is_flip); + + /* Needed for multiple objects to work. */ + BM_mesh_bm_to_me(NULL, + bm, + mesh, + (&(struct BMeshToMeshParams){ + .calc_object_remap = false, + })); + + result = BKE_mesh_from_bmesh_for_eval_nomain(bm, NULL, mesh); + BM_mesh_free(bm); + result->runtime.cd_dirty_vert |= CD_MASK_NORMAL; + } + /* if new mesh returned, return it; otherwise there was + * an error, so delete the modifier object */ + if (result == NULL) { + BKE_modifier_set_error(md, "Cannot execute boolean operation"); + } + } + } + } + FOREACH_COLLECTION_OBJECT_RECURSIVE_END; + } + } + +#ifdef DEBUG_TIME + TIMEIT_END(boolean_bmesh); +#endif + return result; } @@ -392,13 +709,26 @@ static void panel_draw(const bContext *UNUSED(C), Panel *panel) uiLayoutSetPropSep(layout, true); + uiItemR(layout, ptr, "operand_type", 0, NULL, ICON_NONE); + + const bool operand_object = RNA_enum_get(ptr, "operand_type") == eBooleanModifierFlag_Object; + + if (operand_object) { + uiItemR(layout, ptr, "object", 0, NULL, ICON_NONE); + } + else { + uiItemR(layout, ptr, "collection", 0, NULL, ICON_NONE); + } + const bool use_exact = RNA_enum_get(ptr, "solver") == eBooleanModifierSolver_Exact; - uiItemR(layout, ptr, "object", 0, NULL, ICON_NONE); uiItemR(layout, ptr, "solver", UI_ITEM_R_EXPAND, NULL, ICON_NONE); if (use_exact) { - uiItemR(layout, ptr, "use_self", 0, NULL, ICON_NONE); + /* When operand is collection, we always use_self. */ + if (operand_object) { + uiItemR(layout, ptr, "use_self", 0, NULL, ICON_NONE); + } } else { uiItemR(layout, ptr, "double_threshold", 0, NULL, ICON_NONE); @@ -443,7 +773,7 @@ ModifierTypeInfo modifierType_Boolean = { /* dependsOnTime */ NULL, /* dependsOnNormals */ NULL, /* foreachObjectLink */ foreachObjectLink, - /* foreachIDLink */ NULL, + /* foreachIDLink */ foreachIDLink, /* foreachTexLink */ NULL, /* freeRuntimeData */ NULL, /* panelRegister */ panelRegister, |