BMesh: Add option to use BMesh boolean modifier

This uses a bmesh-intersection, BLI_kdtree and watertight intersections to perform boolean operations.

For now keep both BMesh and Carve booleans usable at once for testing & bug reports,
however we plan to phase out Carve by next release.

5 files changed, 268 insertions, 15 deletions

diff --git a/release/scripts/startup/bl_ui/properties_data_modifier.py b/release/scripts/startup/bl_ui/properties_data_modifier.py
index 58896e898c6..98570ca5280 100644
--- a/release/scripts/startup/bl_ui/properties_data_modifier.py
+++ b/release/scripts/startup/bl_ui/properties_data_modifier.py
@@ -156,6 +156,15 @@ class DATA_PT_modifiers(ModifierButtonsPanel, Panel):
         col.label(text="Object:")
         col.prop(md, "object", text="")
 
+        layout.prop(md, "use_bmesh")
+        if md.use_bmesh:
+            box = layout.box()
+            box.label("BMesh Options:")
+            box.prop(md, "use_bmesh_separate")
+            box.prop(md, "use_bmesh_dissolve")
+            box.prop(md, "use_bmesh_connect_regions")
+            box.prop(md, "threshold")
+
     def BUILD(self, layout, ob, md):
         split = layout.split()
 
diff --git a/source/blender/bmesh/intern/bmesh_mesh.h b/source/blender/bmesh/intern/bmesh_mesh.h
index b157237c7d0..b9cdc4ccf66 100644
--- a/source/blender/bmesh/intern/bmesh_mesh.h
+++ b/source/blender/bmesh/intern/bmesh_mesh.h
@@ -94,8 +94,26 @@ extern const BMAllocTemplate bm_mesh_chunksize_default;
 	(bm)->totvert), (bm)->totedge, (bm)->totloop, (bm)->totface}
 #define BMALLOC_TEMPLATE_FROM_ME(me) { (CHECK_TYPE_INLINE(me, Mesh *), \
 	(me)->totvert), (me)->totedge, (me)->totloop, (me)->totpoly}
-#define BMALLOC_TEMPLATE_FROM_DM(dm) { (CHECK_TYPE_INLINE(dm, DerivedMesh *), \
-	(dm)->getNumVerts(dm)), (dm)->getNumEdges(dm), (dm)->getNumLoops(dm), (dm)->getNumPolys(dm)}
+
+#define _VA_BMALLOC_TEMPLATE_FROM_DM_1(dm) { \
+	(CHECK_TYPE_INLINE(dm, DerivedMesh *), \
+	(dm)->getNumVerts(dm)),		\
+	(dm)->getNumEdges(dm),		\
+	(dm)->getNumLoops(dm),		\
+	(dm)->getNumPolys(dm),		\
+	}
+#define _VA_BMALLOC_TEMPLATE_FROM_DM_2(dm_a, dm_b) { \
+	(CHECK_TYPE_INLINE(dm_a, DerivedMesh *), \
+	 CHECK_TYPE_INLINE(dm_b, DerivedMesh *), \
+	(dm_a)->getNumVerts(dm_a)) + (dm_b)->getNumVerts(dm_b),	\
+	(dm_a)->getNumEdges(dm_a)  + (dm_b)->getNumEdges(dm_b),	\
+	(dm_a)->getNumLoops(dm_a)  + (dm_b)->getNumLoops(dm_b),	\
+	(dm_a)->getNumPolys(dm_a)  + (dm_b)->getNumPolys(dm_b),	\
+	}
+
+#define BMALLOC_TEMPLATE_FROM_DM(...) VA_NARGS_CALL_OVERLOAD(_VA_BMALLOC_TEMPLATE_FROM_DM_, __VA_ARGS__)
+
+
 
 enum {
 	BM_MESH_CREATE_USE_TOOLFLAGS = (1 << 0)
diff --git a/source/blender/makesdna/DNA_modifier_types.h b/source/blender/makesdna/DNA_modifier_types.h
index 6f07d18953e..525e267e537 100644
--- a/source/blender/makesdna/DNA_modifier_types.h
+++ b/source/blender/makesdna/DNA_modifier_types.h
@@ -640,7 +640,9 @@ typedef struct BooleanModifierData {
 	ModifierData modifier;
 
 	struct Object *object;
-	int operation, pad;
+	char operation;
+	char bm_flag, pad[2];
+	float threshold;
 } BooleanModifierData;
 
 typedef enum {
@@ -649,6 +651,14 @@ typedef enum {
 	eBooleanModifierOp_Difference = 2,
 } BooleanModifierOp;
 
+/* temp bm_flag (debugging only) */
+enum {
+	eBooleanModifierBMeshFlag_Enabled                   = (1 << 0),
+	eBooleanModifierBMeshFlag_BMesh_Separate            = (1 << 1),
+	eBooleanModifierBMeshFlag_BMesh_NoDissolve          = (1 << 2),
+	eBooleanModifierBMeshFlag_BMesh_NoConnectRegions    = (1 << 3),
+};
+
 typedef struct MDefInfluence {
 	int vertex;
 	float weight;
diff --git a/source/blender/makesrna/intern/rna_modifier.c b/source/blender/makesrna/intern/rna_modifier.c
index 4ca7493eb13..bf35752dcf6 100644
--- a/source/blender/makesrna/intern/rna_modifier.c
+++ b/source/blender/makesrna/intern/rna_modifier.c
@@ -1883,6 +1883,34 @@ static void rna_def_modifier_boolean(BlenderRNA *brna)
 	RNA_def_property_enum_items(prop, prop_operation_items);
 	RNA_def_property_ui_text(prop, "Operation", "");
 	RNA_def_property_update(prop, 0, "rna_Modifier_update");
+
+	/* BMesh intersection options */
+	prop = RNA_def_property(srna, "use_bmesh", PROP_BOOLEAN, PROP_NONE);
+	RNA_def_property_boolean_sdna(prop, NULL, "bm_flag", eBooleanModifierBMeshFlag_Enabled);
+	RNA_def_property_ui_text(prop, "Use BMesh", "Use BMesh boolean calculation");
+	RNA_def_property_update(prop, 0, "rna_Modifier_update");
+
+	prop = RNA_def_property(srna, "use_bmesh_separate", PROP_BOOLEAN, PROP_NONE);
+	RNA_def_property_boolean_sdna(prop, NULL, "bm_flag", eBooleanModifierBMeshFlag_BMesh_Separate);
+	RNA_def_property_ui_text(prop, "Separate", "Keep edges separate");
+	RNA_def_property_update(prop, 0, "rna_Modifier_update");
+
+	prop = RNA_def_property(srna, "use_bmesh_dissolve", PROP_BOOLEAN, PROP_NONE);
+	RNA_def_property_boolean_negative_sdna(prop, NULL, "bm_flag", eBooleanModifierBMeshFlag_BMesh_NoDissolve);
+	RNA_def_property_ui_text(prop, "Dissolve", "Dissolve verts created from tessellated intersection");
+	RNA_def_property_update(prop, 0, "rna_Modifier_update");
+
+	prop = RNA_def_property(srna, "use_bmesh_connect_regions", PROP_BOOLEAN, PROP_NONE);
+	RNA_def_property_boolean_negative_sdna(prop, NULL, "bm_flag", eBooleanModifierBMeshFlag_BMesh_NoConnectRegions);
+	RNA_def_property_ui_text(prop, "Calculate Holes", "Connect regions (needed for hole filling)");
+	RNA_def_property_update(prop, 0, "rna_Modifier_update");
+
+	prop = RNA_def_property(srna, "threshold", PROP_FLOAT, PROP_DISTANCE);
+	RNA_def_property_float_sdna(prop, NULL, "threshold");
+	RNA_def_property_range(prop, 0, 1.0f);
+	RNA_def_property_ui_range(prop, 0, 1, 1, 7);
+	RNA_def_property_ui_text(prop, "Threshold",  "");
+	RNA_def_property_update(prop, 0, "rna_Modifier_update");
 }
 
 static void rna_def_modifier_array(BlenderRNA *brna)
diff --git a/source/blender/modifiers/intern/MOD_boolean.c b/source/blender/modifiers/intern/MOD_boolean.c
index 3fd2c8a3502..03adf3c0901 100644
--- a/source/blender/modifiers/intern/MOD_boolean.c
+++ b/source/blender/modifiers/intern/MOD_boolean.c
@@ -1,4 +1,3 @@
-
 /*
  * ***** BEGIN GPL LICENSE BLOCK *****
  *
@@ -33,6 +32,11 @@
  *  \ingroup modifiers
  */
 
+#define USE_BMESH
+#ifdef WITH_MOD_BOOLEAN
+#  define USE_CARVE WITH_MOD_BOOLEAN
+#endif
+
 #include <stdio.h>
 
 #include "DNA_object_types.h"
@@ -48,6 +52,18 @@
 #include "MOD_boolean_util.h"
 #include "MOD_util.h"
 
+#ifdef USE_BMESH
+#include "BLI_math_geom.h"
+#include "MEM_guardedalloc.h"
+
+#include "bmesh.h"
+#include "bmesh_tools.h"
+#include "tools/bmesh_intersect.h"
+#endif
+
+#include "PIL_time.h"
+#include "PIL_time_utildefines.h"
+
 static void copyData(ModifierData *md, ModifierData *target)
 {
 #if 0
@@ -104,7 +120,8 @@ static void updateDepsgraph(ModifierData *md,
 	DEG_add_object_relation(node, ob, DEG_OB_COMP_TRANSFORM, "Boolean Modifier");
 }
 
-#ifdef WITH_MOD_BOOLEAN
+#if defined(USE_CARVE) || defined(USE_BMESH)
+
 static DerivedMesh *get_quick_derivedMesh(DerivedMesh *derivedData, DerivedMesh *dm, int operation)
 {
 	DerivedMesh *result = NULL;
@@ -129,10 +146,157 @@ static DerivedMesh *get_quick_derivedMesh(DerivedMesh *derivedData, DerivedMesh
 
 	return result;
 }
+#endif  /* defined(USE_CARVE) || defined(USE_BMESH) */
+
+
+/* -------------------------------------------------------------------- */
+/* BMESH */
+
+#ifdef USE_BMESH
+
+/* has no meaning for faces, do this so we can tell which face is which */
+#define BM_FACE_TAG BM_ELEM_DRAW
+
+/**
+ * Compare selected/unselected.
+ */
+static int bm_face_isect_pair(BMFace *f, void *UNUSED(user_data))
+{
+	return BM_elem_flag_test(f, BM_FACE_TAG) ? 1 : 0;
+}
+
+static DerivedMesh *applyModifier_bmesh(
+        ModifierData *md, Object *ob,
+        DerivedMesh *dm,
+        ModifierApplyFlag flag)
+{
+	BooleanModifierData *bmd = (BooleanModifierData *) md;
+	DerivedMesh *dm_other;
+
+	if (!bmd->object)
+		return dm;
+
+	dm_other = get_dm_for_modifier(bmd->object, flag);
+
+	if (dm_other) {
+		DerivedMesh *result;
+
+		/* 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_derivedMesh(dm, dm_other, bmd->operation);
+
+		if (result == NULL) {
+			BMesh *bm;
+			const BMAllocTemplate allocsize = BMALLOC_TEMPLATE_FROM_DM(dm, dm_other);
+
+			TIMEIT_START(boolean_bmesh);
+			bm = BM_mesh_create(&allocsize);
+
+			DM_to_bmesh_ex(dm_other, bm, true);
+			DM_to_bmesh_ex(dm, bm, true);
+
+			if (1) {
+				/* create tessface & intersect */
+				const int looptris_tot = poly_to_tri_count(bm->totface, bm->totloop);
+				int tottri;
+				BMLoop *(*looptris)[3];
+
+				looptris = MEM_mallocN(sizeof(*looptris) * looptris_tot, __func__);
+
+				BM_bmesh_calc_tessellation(bm, looptris, &tottri);
+
+				/* 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 = dm_other->getNumVerts(dm_other);
+					const int i_faces_end = dm_other->getNumPolys(dm_other);
+
+					float imat[4][4];
+					float omat[4][4];
+
+					invert_m4_m4(imat, ob->obmat);
+					mul_m4_m4m4(omat, imat, bmd->object->obmat);
+
+
+					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;
+						}
+					}
+
+					/* we need face normals because of 'BM_face_split_edgenet'
+					 * we could calculate on the fly too (before calling split). */
+					float nmat[4][4];
+					invert_m4_m4(nmat, omat);
+
+					BMFace *efa;
+					i = 0;
+					BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) {
+						mul_transposed_mat3_m4_v3(nmat, efa->no);
+						normalize_v3(efa->no);
+						BM_elem_flag_enable(efa, BM_FACE_TAG);  /* temp tag to test which side split faces are from */
+						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);
+
+				BM_mesh_intersect(
+				        bm,
+				        looptris, tottri,
+				        bm_face_isect_pair, NULL,
+				        false,
+				        (bmd->bm_flag & eBooleanModifierBMeshFlag_BMesh_Separate) != 0,
+				        (bmd->bm_flag & eBooleanModifierBMeshFlag_BMesh_NoDissolve) == 0,
+				        (bmd->bm_flag & eBooleanModifierBMeshFlag_BMesh_NoConnectRegions) == 0,
+				        bmd->operation,
+				        bmd->threshold);
+
+				MEM_freeN(looptris);
+			}
+
+			result = CDDM_from_bmesh(bm, true);
+
+			BM_mesh_free(bm);
+
+			result->dirty |= DM_DIRTY_NORMALS;
+
+			TIMEIT_END(boolean_bmesh);
+
+			return result;
+		}
+
+		/* if new mesh returned, return it; otherwise there was
+		 * an error, so delete the modifier object */
+		if (result)
+			return result;
+		else
+			modifier_setError(md, "Cannot execute boolean operation");
+	}
+
+	return dm;
+}
+#endif  /* USE_BMESH */
+
 
-static DerivedMesh *applyModifier(ModifierData *md, Object *ob,
-                                  DerivedMesh *derivedData,
-                                  ModifierApplyFlag flag)
+/* -------------------------------------------------------------------- */
+/* CARVE */
+
+#ifdef USE_CARVE
+static DerivedMesh *applyModifier_carve(
+        ModifierData *md, Object *ob,
+        DerivedMesh *derivedData,
+        ModifierApplyFlag flag)
 {
 	BooleanModifierData *bmd = (BooleanModifierData *) md;
 	DerivedMesh *dm;
@@ -151,12 +315,12 @@ static DerivedMesh *applyModifier(ModifierData *md, Object *ob,
 		result = get_quick_derivedMesh(derivedData, dm, bmd->operation);
 
 		if (result == NULL) {
-			// TIMEIT_START(NewBooleanDerivedMesh)
+			TIMEIT_START(boolean_carve);
 
 			result = NewBooleanDerivedMesh(dm, bmd->object, derivedData, ob,
 			                               1 + bmd->operation);
 
-			// TIMEIT_END(NewBooleanDerivedMesh)
+			TIMEIT_END(boolean_carve);
 		}
 
 		/* if new mesh returned, return it; otherwise there was
@@ -169,14 +333,16 @@ static DerivedMesh *applyModifier(ModifierData *md, Object *ob,
 	
 	return derivedData;
 }
-#else // WITH_MOD_BOOLEAN
-static DerivedMesh *applyModifier(ModifierData *UNUSED(md), Object *UNUSED(ob),
-                                  DerivedMesh *derivedData,
-                                  ModifierApplyFlag UNUSED(flag))
+#endif  /* USE_CARVE */
+
+
+static DerivedMesh *applyModifier_nop(
+        ModifierData *UNUSED(md), Object *UNUSED(ob),
+        DerivedMesh *derivedData,
+        ModifierApplyFlag UNUSED(flag))
 {
 	return derivedData;
 }
-#endif // WITH_MOD_BOOLEAN
 
 static CustomDataMask requiredDataMask(Object *UNUSED(ob), ModifierData *UNUSED(md))
 {
@@ -187,6 +353,28 @@ static CustomDataMask requiredDataMask(Object *UNUSED(ob), ModifierData *UNUSED(
 	return dataMask;
 }
 
+static DerivedMesh *applyModifier(
+        ModifierData *md, Object *ob,
+        DerivedMesh *derivedData,
+        ModifierApplyFlag flag)
+{
+	BooleanModifierData *bmd = (BooleanModifierData *)md;
+	const int method = (bmd->bm_flag & eBooleanModifierBMeshFlag_Enabled) ? 1 : 0;
+
+	switch (method) {
+#ifdef USE_CARVE
+		case 0:
+			return applyModifier_carve(md, ob, derivedData, flag);
+#endif
+#ifdef USE_BMESH
+		case 1:
+			return applyModifier_bmesh(md, ob, derivedData, flag);
+#endif
+		default:
+			return applyModifier_nop(md, ob, derivedData, flag);
+	}
+}
+
 
 ModifierTypeInfo modifierType_Boolean = {
 	/* name */              "Boolean",