Merge branch 'master' into blender28
[blender.git] / source / blender / modifiers / intern / MOD_boolean.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software  Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2005 by the Blender Foundation.
19  * All rights reserved.
20  *
21  * Contributor(s): Daniel Dunbar
22  *                 Ton Roosendaal,
23  *                 Ben Batt,
24  *                 Brecht Van Lommel,
25  *                 Campbell Barton
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  *
29  */
30
31 /** \file blender/modifiers/intern/MOD_boolean.c
32  *  \ingroup modifiers
33  */
34
35 // #ifdef DEBUG_TIME
36
37 #include <stdio.h>
38
39 #include "DNA_object_types.h"
40
41 #include "BLI_utildefines.h"
42 #include "BLI_math_matrix.h"
43
44 #include "BKE_library_query.h"
45 #include "BKE_modifier.h"
46
47 #include "MOD_util.h"
48
49 #include "BLI_alloca.h"
50 #include "BLI_math_geom.h"
51 #include "BKE_material.h"
52 #include "BKE_global.h"  /* only to check G.debug */
53 #include "BKE_mesh.h"
54 #include "BKE_library.h"
55
56 #include "DNA_mesh_types.h"
57 #include "DNA_meshdata_types.h"
58
59 #include "DEG_depsgraph_query.h"
60
61 #include "MEM_guardedalloc.h"
62
63 #include "bmesh.h"
64 #include "bmesh_tools.h"
65 #include "tools/bmesh_intersect.h"
66
67 #ifdef DEBUG_TIME
68 #  include "PIL_time.h"
69 #  include "PIL_time_utildefines.h"
70 #endif
71
72 static void initData(ModifierData *md)
73 {
74         BooleanModifierData *bmd = (BooleanModifierData *)md;
75
76         bmd->double_threshold = 1e-6f;
77 }
78
79 static bool isDisabled(ModifierData *md, int UNUSED(useRenderParams))
80 {
81         BooleanModifierData *bmd = (BooleanModifierData *) md;
82
83         return !bmd->object;
84 }
85
86 static void foreachObjectLink(
87         ModifierData *md, Object *ob,
88         ObjectWalkFunc walk, void *userData)
89 {
90         BooleanModifierData *bmd = (BooleanModifierData *) md;
91
92         walk(userData, ob, &bmd->object, IDWALK_CB_NOP);
93 }
94
95 static void updateDepsgraph(ModifierData *md, const ModifierUpdateDepsgraphContext *ctx)
96 {
97         BooleanModifierData *bmd = (BooleanModifierData *)md;
98         if (bmd->object != NULL) {
99                 DEG_add_object_relation(ctx->node, bmd->object, DEG_OB_COMP_TRANSFORM, "Boolean Modifier");
100                 DEG_add_object_relation(ctx->node, bmd->object, DEG_OB_COMP_GEOMETRY, "Boolean Modifier");
101         }
102         /* We need own transformation as well. */
103         DEG_add_object_relation(ctx->node, ctx->object, DEG_OB_COMP_TRANSFORM, "Boolean Modifier");
104 }
105
106 static Mesh *get_quick_mesh(
107         Object *ob_self,  Mesh *mesh_self,
108         Object *ob_other, Mesh *mesh_other,
109         int operation)
110 {
111         Mesh *result = NULL;
112
113         if (mesh_self->totpoly == 0 || mesh_other->totpoly == 0) {
114                 switch (operation) {
115                         case eBooleanModifierOp_Intersect:
116                                 result = BKE_mesh_new_nomain(0, 0, 0, 0, 0);
117                                 break;
118
119                         case eBooleanModifierOp_Union:
120                                 if (mesh_self->totpoly != 0) {
121                                         result = mesh_self;
122                                 }
123                                 else {
124                                         BKE_id_copy_ex(NULL, &mesh_other->id, (ID **)&result,
125                                                        LIB_ID_CREATE_NO_MAIN |
126                                                        LIB_ID_CREATE_NO_USER_REFCOUNT |
127                                                        LIB_ID_CREATE_NO_DEG_TAG |
128                                                        LIB_ID_COPY_NO_PREVIEW,
129                                                        false);
130
131                                         float imat[4][4];
132                                         float omat[4][4];
133
134                                         invert_m4_m4(imat, ob_self->obmat);
135                                         mul_m4_m4m4(omat, imat, ob_other->obmat);
136
137                                         const int mverts_len = result->totvert;
138                                         MVert *mv = result->mvert;
139
140                                         for (int i = 0; i < mverts_len; i++, mv++) {
141                                                 mul_m4_v3(omat, mv->co);
142                                         }
143
144                                         result->runtime.cd_dirty_vert |= CD_MASK_NORMAL;
145                                 }
146
147                                 break;
148
149                         case eBooleanModifierOp_Difference:
150                                 result = mesh_self;
151                                 break;
152                 }
153         }
154
155         return result;
156 }
157
158
159 /* has no meaning for faces, do this so we can tell which face is which */
160 #define BM_FACE_TAG BM_ELEM_DRAW
161
162 /**
163  * Compare selected/unselected.
164  */
165 static int bm_face_isect_pair(BMFace *f, void *UNUSED(user_data))
166 {
167         return BM_elem_flag_test(f, BM_FACE_TAG) ? 1 : 0;
168 }
169
170 static Mesh *applyModifier(ModifierData *md, const ModifierEvalContext *ctx, Mesh *mesh)
171 {
172         BooleanModifierData *bmd = (BooleanModifierData *) md;
173         Mesh *result = mesh;
174
175         Mesh *mesh_other;
176         bool mesh_other_free;
177
178         if (!bmd->object) {
179                 return result;
180         }
181
182         Object *ob_eval = DEG_get_evaluated_object(ctx->depsgraph, bmd->object);
183         mesh_other = BKE_modifier_get_evaluated_mesh_from_evaluated_object(ob_eval, &mesh_other_free);
184         if (mesh_other) {
185                 Object *object = ctx->object;
186                 Object *other = bmd->object;
187
188                 /* when one of objects is empty (has got no faces) we could speed up
189                  * calculation a bit returning one of objects' derived meshes (or empty one)
190                  * Returning mesh is depended on modifiers operation (sergey) */
191                 result = get_quick_mesh(object, mesh, other, mesh_other, bmd->operation);
192
193                 if (result == NULL) {
194                         const bool is_flip = (is_negative_m4(object->obmat) != is_negative_m4(other->obmat));
195
196                         BMesh *bm;
197                         const BMAllocTemplate allocsize = BMALLOC_TEMPLATE_FROM_ME(mesh, mesh_other);
198
199 #ifdef DEBUG_TIME
200                         TIMEIT_START(boolean_bmesh);
201 #endif
202                         bm = BM_mesh_create(
203                                  &allocsize,
204                                  &((struct BMeshCreateParams){.use_toolflags = false,}));
205
206                         BM_mesh_bm_from_me(bm, mesh_other, &((struct BMeshFromMeshParams){.calc_face_normal = true,}));
207
208                         if (UNLIKELY(is_flip)) {
209                                 const int cd_loop_mdisp_offset = CustomData_get_offset(&bm->ldata, CD_MDISPS);
210                                 BMIter iter;
211                                 BMFace *efa;
212                                 BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) {
213                                         BM_face_normal_flip_ex(bm, efa, cd_loop_mdisp_offset, true);
214                                 }
215                         }
216
217                         BM_mesh_bm_from_me(bm, mesh, &((struct BMeshFromMeshParams){.calc_face_normal = true,}));
218
219                         /* main bmesh intersection setup */
220                         {
221                                 /* create tessface & intersect */
222                                 const int looptris_tot = poly_to_tri_count(bm->totface, bm->totloop);
223                                 int tottri;
224                                 BMLoop *(*looptris)[3];
225
226                                 looptris = MEM_malloc_arrayN(looptris_tot, sizeof(*looptris), __func__);
227
228                                 BM_mesh_calc_tessellation_beauty(bm, looptris, &tottri);
229
230                                 /* postpone this until after tessellating
231                                  * so we can use the original normals before the vertex are moved */
232                                 {
233                                         BMIter iter;
234                                         int i;
235                                         const int i_verts_end = mesh_other->totvert;
236                                         const int i_faces_end = mesh_other->totpoly;
237
238                                         float imat[4][4];
239                                         float omat[4][4];
240
241                                         invert_m4_m4(imat, object->obmat);
242                                         mul_m4_m4m4(omat, imat, other->obmat);
243
244                                         BMVert *eve;
245                                         i = 0;
246                                         BM_ITER_MESH (eve, &iter, bm, BM_VERTS_OF_MESH) {
247                                                 mul_m4_v3(omat, eve->co);
248                                                 if (++i == i_verts_end) {
249                                                         break;
250                                                 }
251                                         }
252
253                                         /* we need face normals because of 'BM_face_split_edgenet'
254                                          * we could calculate on the fly too (before calling split). */
255                                         {
256                                                 float nmat[3][3];
257                                                 copy_m3_m4(nmat, omat);
258                                                 invert_m3(nmat);
259
260                                                 if (UNLIKELY(is_flip)) {
261                                                         negate_m3(nmat);
262                                                 }
263
264                                                 const short ob_src_totcol = other->totcol;
265                                                 short *material_remap = BLI_array_alloca(material_remap, ob_src_totcol ? ob_src_totcol : 1);
266
267                                                 /* Using original (not evaluated) object here since we are writing to it. */
268                                                 BKE_material_remap_object_calc(ctx->object, other, material_remap);
269
270                                                 BMFace *efa;
271                                                 i = 0;
272                                                 BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) {
273                                                         mul_transposed_m3_v3(nmat, efa->no);
274                                                         normalize_v3(efa->no);
275                                                         BM_elem_flag_enable(efa, BM_FACE_TAG);  /* temp tag to test which side split faces are from */
276
277                                                         /* remap material */
278                                                         if (LIKELY(efa->mat_nr < ob_src_totcol)) {
279                                                                 efa->mat_nr = material_remap[efa->mat_nr];
280                                                         }
281
282                                                         if (++i == i_faces_end) {
283                                                                 break;
284                                                         }
285                                                 }
286                                         }
287                                 }
288
289                                 /* not needed, but normals for 'dm' will be invalid,
290                                  * currently this is ok for 'BM_mesh_intersect' */
291                                 // BM_mesh_normals_update(bm);
292
293                                 bool use_separate = false;
294                                 bool use_dissolve = true;
295                                 bool use_island_connect = true;
296
297                                 /* change for testing */
298                                 if (G.debug & G_DEBUG) {
299                                         use_separate = (bmd->bm_flag & eBooleanModifierBMeshFlag_BMesh_Separate) != 0;
300                                         use_dissolve = (bmd->bm_flag & eBooleanModifierBMeshFlag_BMesh_NoDissolve) == 0;
301                                         use_island_connect = (bmd->bm_flag & eBooleanModifierBMeshFlag_BMesh_NoConnectRegions) == 0;
302                                 }
303
304                                 BM_mesh_intersect(
305                                         bm,
306                                         looptris, tottri,
307                                         bm_face_isect_pair, NULL,
308                                         false,
309                                         use_separate,
310                                         use_dissolve,
311                                         use_island_connect,
312                                         false,
313                                         false,
314                                         bmd->operation,
315                                         bmd->double_threshold);
316
317                                 MEM_freeN(looptris);
318                         }
319
320                         result = BKE_bmesh_to_mesh_nomain(bm, &((struct BMeshToMeshParams){0}));
321
322                         BM_mesh_free(bm);
323
324                         result->runtime.cd_dirty_vert |= CD_MASK_NORMAL;
325
326 #ifdef DEBUG_TIME
327                         TIMEIT_END(boolean_bmesh);
328 #endif
329                 }
330
331                 /* if new mesh returned, return it; otherwise there was
332                  * an error, so delete the modifier object */
333                 if (result == NULL)
334                         modifier_setError(md, "Cannot execute boolean operation");
335         }
336
337         if (mesh_other != NULL && mesh_other_free) {
338                 BKE_id_free(NULL, mesh_other);
339         }
340
341         return result;
342 }
343
344 static CustomDataMask requiredDataMask(Object *UNUSED(ob), ModifierData *UNUSED(md))
345 {
346         CustomDataMask dataMask = CD_MASK_MTFACE | CD_MASK_MEDGE;
347
348         dataMask |= CD_MASK_MDEFORMVERT;
349         
350         return dataMask;
351 }
352
353 ModifierTypeInfo modifierType_Boolean = {
354         /* name */              "Boolean",
355         /* structName */        "BooleanModifierData",
356         /* structSize */        sizeof(BooleanModifierData),
357         /* type */              eModifierTypeType_Nonconstructive,
358         /* flags */             eModifierTypeFlag_AcceptsMesh |
359                                 eModifierTypeFlag_UsesPointCache,
360
361         /* copyData */          modifier_copyData_generic,
362
363         /* deformVerts_DM */    NULL,
364         /* deformMatrices_DM */ NULL,
365         /* deformVertsEM_DM */  NULL,
366         /* deformMatricesEM_DM*/NULL,
367         /* applyModifier_DM */  NULL,
368         /* applyModifierEM_DM */NULL,
369
370         /* deformVerts */       NULL,
371         /* deformMatrices */    NULL,
372         /* deformVertsEM */     NULL,
373         /* deformMatricesEM */  NULL,
374         /* applyModifier */     applyModifier,
375         /* applyModifierEM */   NULL,
376
377         /* initData */          initData,
378         /* requiredDataMask */  requiredDataMask,
379         /* freeData */          NULL,
380         /* isDisabled */        isDisabled,
381         /* updateDepsgraph */   updateDepsgraph,
382         /* dependsOnTime */     NULL,
383         /* dependsOnNormals */  NULL,
384         /* foreachObjectLink */ foreachObjectLink,
385         /* foreachIDLink */     NULL,
386         /* foreachTexLink */    NULL,
387 };