Fix T52291: Boolean fails w/ co-linear edged ngons
[blender-staging.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 #define USE_BMESH
37 #ifdef WITH_MOD_BOOLEAN
38 #  define USE_CARVE WITH_MOD_BOOLEAN
39 #endif
40
41 #include <stdio.h>
42
43 #include "DNA_object_types.h"
44
45 #include "BLI_utildefines.h"
46 #include "BLI_math_matrix.h"
47
48 #include "BKE_cdderivedmesh.h"
49 #include "BKE_library_query.h"
50 #include "BKE_modifier.h"
51
52 #include "depsgraph_private.h"
53
54 #include "MOD_boolean_util.h"
55 #include "MOD_util.h"
56
57
58 #ifdef USE_BMESH
59 #include "BLI_alloca.h"
60 #include "BLI_math_geom.h"
61 #include "BKE_material.h"
62 #include "MEM_guardedalloc.h"
63
64 #include "bmesh.h"
65 #include "bmesh_tools.h"
66 #include "tools/bmesh_intersect.h"
67 #endif
68
69 #ifdef DEBUG_TIME
70 #include "PIL_time.h"
71 #include "PIL_time_utildefines.h"
72 #endif
73
74 static void initData(ModifierData *md)
75 {
76         BooleanModifierData *bmd = (BooleanModifierData *)md;
77
78         bmd->solver = eBooleanModifierSolver_BMesh;
79         bmd->double_threshold = 1e-6f;
80 }
81
82 static void copyData(ModifierData *md, ModifierData *target)
83 {
84 #if 0
85         BooleanModifierData *bmd = (BooleanModifierData *) md;
86         BooleanModifierData *tbmd = (BooleanModifierData *) target;
87 #endif
88         modifier_copyData_generic(md, target);
89 }
90
91 static bool isDisabled(ModifierData *md, int UNUSED(useRenderParams))
92 {
93         BooleanModifierData *bmd = (BooleanModifierData *) md;
94
95         return !bmd->object;
96 }
97
98 static void foreachObjectLink(
99         ModifierData *md, Object *ob,
100         ObjectWalkFunc walk, void *userData)
101 {
102         BooleanModifierData *bmd = (BooleanModifierData *) md;
103
104         walk(userData, ob, &bmd->object, IDWALK_CB_NOP);
105 }
106
107 static void updateDepgraph(ModifierData *md, DagForest *forest,
108                            struct Main *UNUSED(bmain),
109                            struct Scene *UNUSED(scene),
110                            Object *UNUSED(ob),
111                            DagNode *obNode)
112 {
113         BooleanModifierData *bmd = (BooleanModifierData *) md;
114
115         if (bmd->object) {
116                 DagNode *curNode = dag_get_node(forest, bmd->object);
117
118                 dag_add_relation(forest, curNode, obNode,
119                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Boolean Modifier");
120         }
121 }
122
123 static void updateDepsgraph(ModifierData *md,
124                             struct Main *UNUSED(bmain),
125                             struct Scene *UNUSED(scene),
126                             Object *ob,
127                             struct DepsNodeHandle *node)
128 {
129         BooleanModifierData *bmd = (BooleanModifierData *)md;
130         if (bmd->object != NULL) {
131                 DEG_add_object_relation(node, bmd->object, DEG_OB_COMP_TRANSFORM, "Boolean Modifier");
132                 DEG_add_object_relation(node, bmd->object, DEG_OB_COMP_GEOMETRY, "Boolean Modifier");
133         }
134         /* We need own transformation as well. */
135         DEG_add_object_relation(node, ob, DEG_OB_COMP_TRANSFORM, "Boolean Modifier");
136 }
137
138 #if defined(USE_CARVE) || defined(USE_BMESH)
139
140 static DerivedMesh *get_quick_derivedMesh(
141         Object *ob_self,  DerivedMesh *dm_self,
142         Object *ob_other, DerivedMesh *dm_other,
143         int operation)
144 {
145         DerivedMesh *result = NULL;
146
147         if (dm_self->getNumPolys(dm_self) == 0 || dm_other->getNumPolys(dm_other) == 0) {
148                 switch (operation) {
149                         case eBooleanModifierOp_Intersect:
150                                 result = CDDM_new(0, 0, 0, 0, 0);
151                                 break;
152
153                         case eBooleanModifierOp_Union:
154                                 if (dm_self->getNumPolys(dm_self) != 0) {
155                                         result = dm_self;
156                                 }
157                                 else {
158                                         result = CDDM_copy(dm_other);
159
160                                         float imat[4][4];
161                                         float omat[4][4];
162
163                                         invert_m4_m4(imat, ob_self->obmat);
164                                         mul_m4_m4m4(omat, imat, ob_other->obmat);
165
166                                         const int mverts_len = result->getNumVerts(result);
167                                         MVert *mv = CDDM_get_verts(result);
168
169                                         for (int i = 0; i < mverts_len; i++, mv++) {
170                                                 mul_m4_v3(omat, mv->co);
171                                         }
172
173                                         result->dirty |= DM_DIRTY_NORMALS;
174                                 }
175
176                                 break;
177
178                         case eBooleanModifierOp_Difference:
179                                 result = dm_self;
180                                 break;
181                 }
182         }
183
184         return result;
185 }
186 #endif  /* defined(USE_CARVE) || defined(USE_BMESH) */
187
188
189 /* -------------------------------------------------------------------- */
190 /* BMESH */
191
192 #ifdef USE_BMESH
193
194 /* has no meaning for faces, do this so we can tell which face is which */
195 #define BM_FACE_TAG BM_ELEM_DRAW
196
197 /**
198  * Compare selected/unselected.
199  */
200 static int bm_face_isect_pair(BMFace *f, void *UNUSED(user_data))
201 {
202         return BM_elem_flag_test(f, BM_FACE_TAG) ? 1 : 0;
203 }
204
205 static DerivedMesh *applyModifier_bmesh(
206         ModifierData *md, Object *ob,
207         DerivedMesh *dm,
208         ModifierApplyFlag flag)
209 {
210         BooleanModifierData *bmd = (BooleanModifierData *) md;
211         DerivedMesh *dm_other;
212
213         if (!bmd->object)
214                 return dm;
215
216         dm_other = get_dm_for_modifier(bmd->object, flag);
217
218         if (dm_other) {
219                 DerivedMesh *result;
220
221                 /* when one of objects is empty (has got no faces) we could speed up
222                  * calculation a bit returning one of objects' derived meshes (or empty one)
223                  * Returning mesh is depended on modifiers operation (sergey) */
224                 result = get_quick_derivedMesh(ob, dm, bmd->object, dm_other, bmd->operation);
225
226                 if (result == NULL) {
227                         BMesh *bm;
228                         const BMAllocTemplate allocsize = BMALLOC_TEMPLATE_FROM_DM(dm, dm_other);
229
230 #ifdef DEBUG_TIME
231                         TIMEIT_START(boolean_bmesh);
232 #endif
233                         bm = BM_mesh_create(
234                                  &allocsize,
235                                  &((struct BMeshCreateParams){.use_toolflags = false,}));
236
237                         DM_to_bmesh_ex(dm_other, bm, true);
238                         DM_to_bmesh_ex(dm, bm, true);
239
240                         /* main bmesh intersection setup */
241                         {
242                                 /* create tessface & intersect */
243                                 const int looptris_tot = poly_to_tri_count(bm->totface, bm->totloop);
244                                 int tottri;
245                                 BMLoop *(*looptris)[3];
246
247                                 looptris = MEM_mallocN(sizeof(*looptris) * looptris_tot, __func__);
248
249                                 BM_mesh_calc_tessellation_beauty(bm, looptris, &tottri);
250
251                                 /* postpone this until after tessellating
252                                  * so we can use the original normals before the vertex are moved */
253                                 {
254                                         BMIter iter;
255                                         int i;
256                                         const int i_verts_end = dm_other->getNumVerts(dm_other);
257                                         const int i_faces_end = dm_other->getNumPolys(dm_other);
258
259                                         float imat[4][4];
260                                         float omat[4][4];
261
262                                         invert_m4_m4(imat, ob->obmat);
263                                         mul_m4_m4m4(omat, imat, bmd->object->obmat);
264
265
266                                         BMVert *eve;
267                                         i = 0;
268                                         BM_ITER_MESH (eve, &iter, bm, BM_VERTS_OF_MESH) {
269                                                 mul_m4_v3(omat, eve->co);
270                                                 if (++i == i_verts_end) {
271                                                         break;
272                                                 }
273                                         }
274
275                                         /* we need face normals because of 'BM_face_split_edgenet'
276                                          * we could calculate on the fly too (before calling split). */
277                                         {
278                                                 float nmat[4][4];
279                                                 invert_m4_m4(nmat, omat);
280
281                                                 const short ob_src_totcol = bmd->object->totcol;
282                                                 short *material_remap = BLI_array_alloca(material_remap, ob_src_totcol ? ob_src_totcol : 1);
283
284                                                 BKE_material_remap_object_calc(ob, bmd->object, material_remap);
285
286                                                 BMFace *efa;
287                                                 i = 0;
288                                                 BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) {
289                                                         mul_transposed_mat3_m4_v3(nmat, efa->no);
290                                                         normalize_v3(efa->no);
291                                                         BM_elem_flag_enable(efa, BM_FACE_TAG);  /* temp tag to test which side split faces are from */
292
293                                                         /* remap material */
294                                                         if (LIKELY(efa->mat_nr < ob_src_totcol)) {
295                                                                 efa->mat_nr = material_remap[efa->mat_nr];
296                                                         }
297
298                                                         if (++i == i_faces_end) {
299                                                                 break;
300                                                         }
301                                                 }
302                                         }
303                                 }
304
305                                 /* not needed, but normals for 'dm' will be invalid,
306                                  * currently this is ok for 'BM_mesh_intersect' */
307                                 // BM_mesh_normals_update(bm);
308
309                                 /* change for testing */
310                                 bool use_separate = false;
311                                 bool use_dissolve = true;
312                                 bool use_island_connect = true;
313
314                                 BM_mesh_intersect(
315                                         bm,
316                                         looptris, tottri,
317                                         bm_face_isect_pair, NULL,
318                                         false,
319                                         use_separate,
320                                         use_dissolve,
321                                         use_island_connect,
322                                         false,
323                                         bmd->operation,
324                                         bmd->double_threshold);
325
326                                 MEM_freeN(looptris);
327                         }
328
329                         result = CDDM_from_bmesh(bm, true);
330
331                         BM_mesh_free(bm);
332
333                         result->dirty |= DM_DIRTY_NORMALS;
334
335 #ifdef DEBUG_TIME
336                         TIMEIT_END(boolean_bmesh);
337 #endif
338
339                         return result;
340                 }
341
342                 /* if new mesh returned, return it; otherwise there was
343                  * an error, so delete the modifier object */
344                 if (result)
345                         return result;
346                 else
347                         modifier_setError(md, "Cannot execute boolean operation");
348         }
349
350         return dm;
351 }
352 #endif  /* USE_BMESH */
353
354
355 /* -------------------------------------------------------------------- */
356 /* CARVE */
357
358 #ifdef USE_CARVE
359 static DerivedMesh *applyModifier_carve(
360         ModifierData *md, Object *ob,
361         DerivedMesh *derivedData,
362         ModifierApplyFlag flag)
363 {
364         BooleanModifierData *bmd = (BooleanModifierData *) md;
365         DerivedMesh *dm;
366
367         if (!bmd->object)
368                 return derivedData;
369
370         dm = get_dm_for_modifier(bmd->object, flag);
371
372         if (dm) {
373                 DerivedMesh *result;
374
375                 /* when one of objects is empty (has got no faces) we could speed up
376                  * calculation a bit returning one of objects' derived meshes (or empty one)
377                  * Returning mesh is depended on modifiers operation (sergey) */
378                 result = get_quick_derivedMesh(ob, derivedData, bmd->object, dm, bmd->operation);
379
380                 if (result == NULL) {
381 #ifdef DEBUG_TIME
382                         TIMEIT_START(boolean_carve);
383 #endif
384
385                         result = NewBooleanDerivedMesh(dm, bmd->object, derivedData, ob,
386                                                        1 + bmd->operation);
387 #ifdef DEBUG_TIME
388                         TIMEIT_END(boolean_carve);
389 #endif
390                 }
391
392                 /* if new mesh returned, return it; otherwise there was
393                  * an error, so delete the modifier object */
394                 if (result)
395                         return result;
396                 else
397                         modifier_setError(md, "Cannot execute boolean operation");
398         }
399         
400         return derivedData;
401 }
402 #endif  /* USE_CARVE */
403
404
405 static DerivedMesh *applyModifier_nop(
406         ModifierData *UNUSED(md), Object *UNUSED(ob),
407         DerivedMesh *derivedData,
408         ModifierApplyFlag UNUSED(flag))
409 {
410         return derivedData;
411 }
412
413 static CustomDataMask requiredDataMask(Object *UNUSED(ob), ModifierData *UNUSED(md))
414 {
415         CustomDataMask dataMask = CD_MASK_MTFACE | CD_MASK_MEDGE;
416
417         dataMask |= CD_MASK_MDEFORMVERT;
418         
419         return dataMask;
420 }
421
422 static DerivedMesh *applyModifier(
423         ModifierData *md, Object *ob,
424         DerivedMesh *derivedData,
425         ModifierApplyFlag flag)
426 {
427         BooleanModifierData *bmd = (BooleanModifierData *)md;
428
429         switch (bmd->solver) {
430 #ifdef USE_CARVE
431                 case eBooleanModifierSolver_Carve:
432                         return applyModifier_carve(md, ob, derivedData, flag);
433 #endif
434 #ifdef USE_BMESH
435                 case eBooleanModifierSolver_BMesh:
436                         return applyModifier_bmesh(md, ob, derivedData, flag);
437 #endif
438                 default:
439                         return applyModifier_nop(md, ob, derivedData, flag);
440         }
441 }
442
443
444 ModifierTypeInfo modifierType_Boolean = {
445         /* name */              "Boolean",
446         /* structName */        "BooleanModifierData",
447         /* structSize */        sizeof(BooleanModifierData),
448         /* type */              eModifierTypeType_Nonconstructive,
449         /* flags */             eModifierTypeFlag_AcceptsMesh |
450                                 eModifierTypeFlag_UsesPointCache,
451
452         /* copyData */          copyData,
453         /* deformVerts */       NULL,
454         /* deformMatrices */    NULL,
455         /* deformVertsEM */     NULL,
456         /* deformMatricesEM */  NULL,
457         /* applyModifier */     applyModifier,
458         /* applyModifierEM */   NULL,
459         /* initData */          initData,
460         /* requiredDataMask */  requiredDataMask,
461         /* freeData */          NULL,
462         /* isDisabled */        isDisabled,
463         /* updateDepgraph */    updateDepgraph,
464         /* updateDepsgraph */   updateDepsgraph,
465         /* dependsOnTime */     NULL,
466         /* dependsOnNormals */  NULL,
467         /* foreachObjectLink */ foreachObjectLink,
468         /* foreachIDLink */     NULL,
469         /* foreachTexLink */    NULL,
470 };