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