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