Fix T60244: Bisect in mirror modifier doesn't work properly.
[blender.git] / source / blender / modifiers / intern / MOD_mirror.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_mirror.c
32  *  \ingroup modifiers
33  */
34
35
36 #include "DNA_mesh_types.h"
37 #include "DNA_meshdata_types.h"
38 #include "DNA_object_types.h"
39
40 #include "BLI_math.h"
41
42 #include "BKE_library.h"
43 #include "BKE_library_query.h"
44 #include "BKE_mesh.h"
45 #include "BKE_modifier.h"
46 #include "BKE_deform.h"
47
48 #include "bmesh.h"
49 #include "bmesh_tools.h"
50
51 #include "MEM_guardedalloc.h"
52
53 #include "DEG_depsgraph_build.h"
54 #include "DEG_depsgraph_query.h"
55
56 #include "MOD_modifiertypes.h"
57
58 static void initData(ModifierData *md)
59 {
60         MirrorModifierData *mmd = (MirrorModifierData *) md;
61
62         mmd->flag |= (MOD_MIR_AXIS_X | MOD_MIR_VGROUP);
63         mmd->tolerance = 0.001;
64         mmd->mirror_ob = NULL;
65 }
66
67 static void foreachObjectLink(
68         ModifierData *md, Object *ob,
69         ObjectWalkFunc walk, void *userData)
70 {
71         MirrorModifierData *mmd = (MirrorModifierData *) md;
72
73         walk(userData, ob, &mmd->mirror_ob, IDWALK_CB_NOP);
74 }
75
76 static void updateDepsgraph(ModifierData *md, const ModifierUpdateDepsgraphContext *ctx)
77 {
78         MirrorModifierData *mmd = (MirrorModifierData *)md;
79         if (mmd->mirror_ob != NULL) {
80                 DEG_add_object_relation(ctx->node, mmd->mirror_ob, DEG_OB_COMP_TRANSFORM, "Mirror Modifier");
81                 DEG_add_object_relation(ctx->node, ctx->object, DEG_OB_COMP_TRANSFORM, "Mirror Modifier");
82         }
83 }
84
85 static Mesh *doBiscetOnMirrorPlane(
86         MirrorModifierData *mmd,
87         const Mesh *mesh,
88         int axis,
89         float plane_co[3],
90         float plane_no[3])
91 {
92         bool do_bisect_flip_axis = (
93                 (axis == 0 && mmd->flag & MOD_MIR_BISECT_FLIP_AXIS_X) ||
94                 (axis == 1 && mmd->flag & MOD_MIR_BISECT_FLIP_AXIS_Y) ||
95                 (axis == 2 && mmd->flag & MOD_MIR_BISECT_FLIP_AXIS_Z));
96
97         const float bisect_distance = 0.001f;
98
99         Mesh *result;
100         BMesh *bm;
101         BMIter viter;
102         BMVert *v, *v_next;
103
104         bm = BKE_mesh_to_bmesh_ex(
105                 mesh,
106                 &(struct BMeshCreateParams){0},
107                 &(struct BMeshFromMeshParams){
108                         .calc_face_normal = true,
109                         .cd_mask_extra = CD_MASK_ORIGINDEX,
110                 });
111
112         /* Define bisecting plane (aka mirror plane). */
113         float plane[4];
114         if (!do_bisect_flip_axis) {
115                 /* That reversed condition is a tad weird, but for some reason that's how you keep
116                  * the part of the mesh which is on the non-mirrored side when flip option is disabled,
117                  * think that that is the expected behavior. */
118                 negate_v3(plane_no);
119         }
120         plane_from_point_normal_v3(plane, plane_co, plane_no);
121
122         BM_mesh_bisect_plane(bm, plane, false, false, 0, 0, bisect_distance);
123
124         /* Plane definitions for vert killing. */
125         float plane_offset[4];
126         copy_v3_v3(plane_offset, plane);
127         plane_offset[3] = plane[3] - bisect_distance;
128
129         /* Delete verts across the mirror plane. */
130         BM_ITER_MESH_MUTABLE(v, v_next, &viter, bm, BM_VERTS_OF_MESH) {
131                 if (plane_point_side_v3(plane_offset, v->co) > 0.0f) {
132                         BM_vert_kill(bm, v);
133                 }
134         }
135
136         result = BKE_mesh_from_bmesh_for_eval_nomain(bm, 0);
137         BM_mesh_free(bm);
138
139         return result;
140 }
141
142 static Mesh *doMirrorOnAxis(
143         MirrorModifierData *mmd,
144         const ModifierEvalContext *ctx,
145         Object *ob,
146         const Mesh *mesh,
147         int axis)
148 {
149         const float tolerance_sq = mmd->tolerance * mmd->tolerance;
150         const bool do_vtargetmap = (mmd->flag & MOD_MIR_NO_MERGE) == 0;
151         int tot_vtargetmap = 0;  /* total merge vertices */
152
153         const bool do_bisect = (
154                 (axis == 0 && mmd->flag & MOD_MIR_BISECT_AXIS_X) ||
155                 (axis == 1 && mmd->flag & MOD_MIR_BISECT_AXIS_Y) ||
156                 (axis == 2 && mmd->flag & MOD_MIR_BISECT_AXIS_Z));
157
158         Mesh *result;
159         MVert *mv, *mv_prev;
160         MEdge *me;
161         MLoop *ml;
162         MPoly *mp;
163         float mtx[4][4];
164         float plane_co[3], plane_no[3];
165         int i;
166         int a, totshape;
167         int *vtargetmap = NULL, *vtmap_a = NULL, *vtmap_b = NULL;
168
169         /* mtx is the mirror transformation */
170         unit_m4(mtx);
171         mtx[axis][axis] = -1.0f;
172
173         Object *mirror_ob = DEG_get_evaluated_object(ctx->depsgraph, mmd->mirror_ob);
174         if (mirror_ob != NULL) {
175                 float tmp[4][4];
176                 float itmp[4][4];
177
178                 /* tmp is a transform from coords relative to the object's own origin,
179                  * to coords relative to the mirror object origin */
180                 invert_m4_m4(tmp, mirror_ob->obmat);
181                 mul_m4_m4m4(tmp, tmp, ob->obmat);
182
183                 /* itmp is the reverse transform back to origin-relative coordinates */
184                 invert_m4_m4(itmp, tmp);
185
186                 /* combine matrices to get a single matrix that translates coordinates into
187                  * mirror-object-relative space, does the mirror, and translates back to
188                  * origin-relative space */
189                 mul_m4_series(mtx, itmp, mtx, tmp);
190
191                 if (do_bisect) {
192                         copy_v3_v3(plane_co, itmp[3]);
193                         copy_v3_v3(plane_no, itmp[axis]);
194                 }
195         }
196         else if(do_bisect) {
197                 copy_v3_v3(plane_co, mtx[3]);
198                 /* Need to negate here, since that axis is inverted (for mirror transform). */
199                 negate_v3_v3(plane_no, mtx[axis]);
200         }
201
202         Mesh *mesh_bisect = NULL;
203         if (do_bisect) {
204                 mesh_bisect = doBiscetOnMirrorPlane(mmd, mesh, axis, plane_co, plane_no);
205                 mesh = mesh_bisect;
206         }
207
208         const int maxVerts = mesh->totvert;
209         const int maxEdges = mesh->totedge;
210         const int maxLoops = mesh->totloop;
211         const int maxPolys = mesh->totpoly;
212
213         result = BKE_mesh_new_nomain_from_template(
214                 mesh, maxVerts * 2, maxEdges * 2, 0, maxLoops * 2, maxPolys * 2);
215
216         /*copy customdata to original geometry*/
217         CustomData_copy_data(&mesh->vdata, &result->vdata, 0, 0, maxVerts);
218         CustomData_copy_data(&mesh->edata, &result->edata, 0, 0, maxEdges);
219         CustomData_copy_data(&mesh->ldata, &result->ldata, 0, 0, maxLoops);
220         CustomData_copy_data(&mesh->pdata, &result->pdata, 0, 0, maxPolys);
221
222         /* Subsurf for eg won't have mesh data in the custom data arrays.
223          * now add mvert/medge/mpoly layers. */
224         if (!CustomData_has_layer(&mesh->vdata, CD_MVERT)) {
225                 memcpy(result->mvert, mesh->mvert, sizeof(*result->mvert) * mesh->totvert);
226         }
227         if (!CustomData_has_layer(&mesh->edata, CD_MEDGE)) {
228                 memcpy(result->medge, mesh->medge, sizeof(*result->medge) * mesh->totedge);
229         }
230         if (!CustomData_has_layer(&mesh->pdata, CD_MPOLY)) {
231                 memcpy(result->mloop, mesh->mloop, sizeof(*result->mloop) * mesh->totloop);
232                 memcpy(result->mpoly, mesh->mpoly, sizeof(*result->mpoly) * mesh->totpoly);
233         }
234
235         /* copy customdata to new geometry,
236          * copy from its self because this data may have been created in the checks above */
237         CustomData_copy_data(&result->vdata, &result->vdata, 0, maxVerts, maxVerts);
238         CustomData_copy_data(&result->edata, &result->edata, 0, maxEdges, maxEdges);
239         /* loops are copied later */
240         CustomData_copy_data(&result->pdata, &result->pdata, 0, maxPolys, maxPolys);
241
242         if (do_vtargetmap) {
243                 /* second half is filled with -1 */
244                 vtargetmap = MEM_malloc_arrayN(maxVerts, 2 * sizeof(int), "MOD_mirror tarmap");
245
246                 vtmap_a = vtargetmap;
247                 vtmap_b = vtargetmap + maxVerts;
248         }
249
250         /* mirror vertex coordinates */
251         mv_prev = result->mvert;
252         mv = mv_prev + maxVerts;
253         for (i = 0; i < maxVerts; i++, mv++, mv_prev++) {
254                 mul_m4_v3(mtx, mv->co);
255
256                 if (do_vtargetmap) {
257                         /* compare location of the original and mirrored vertex, to see if they
258                          * should be mapped for merging */
259                         if (UNLIKELY(len_squared_v3v3(mv_prev->co, mv->co) < tolerance_sq)) {
260                                 *vtmap_a = maxVerts + i;
261                                 tot_vtargetmap++;
262
263                                 /* average location */
264                                 mid_v3_v3v3(mv->co, mv_prev->co, mv->co);
265                                 copy_v3_v3(mv_prev->co, mv->co);
266                         }
267                         else {
268                                 *vtmap_a = -1;
269                         }
270
271                         *vtmap_b = -1; /* fill here to avoid 2x loops */
272
273                         vtmap_a++;
274                         vtmap_b++;
275                 }
276         }
277
278         /* handle shape keys */
279         totshape = CustomData_number_of_layers(&result->vdata, CD_SHAPEKEY);
280         for (a = 0; a < totshape; a++) {
281                 float (*cos)[3] = CustomData_get_layer_n(&result->vdata, CD_SHAPEKEY, a);
282                 for (i = maxVerts; i < result->totvert; i++) {
283                         mul_m4_v3(mtx, cos[i]);
284                 }
285         }
286
287         /* adjust mirrored edge vertex indices */
288         me = result->medge + maxEdges;
289         for (i = 0; i < maxEdges; i++, me++) {
290                 me->v1 += maxVerts;
291                 me->v2 += maxVerts;
292         }
293
294         /* adjust mirrored poly loopstart indices, and reverse loop order (normals) */
295         mp = result->mpoly + maxPolys;
296         ml = result->mloop;
297         for (i = 0; i < maxPolys; i++, mp++) {
298                 MLoop *ml2;
299                 int j, e;
300
301                 /* reverse the loop, but we keep the first vertex in the face the same,
302                  * to ensure that quads are split the same way as on the other side */
303                 CustomData_copy_data(&result->ldata, &result->ldata, mp->loopstart, mp->loopstart + maxLoops, 1);
304
305                 for (j = 1; j < mp->totloop; j++)
306                         CustomData_copy_data(&result->ldata, &result->ldata,
307                                              mp->loopstart + j,
308                                              mp->loopstart + maxLoops + mp->totloop - j,
309                                              1);
310
311                 ml2 = ml + mp->loopstart + maxLoops;
312                 e = ml2[0].e;
313                 for (j = 0; j < mp->totloop - 1; j++) {
314                         ml2[j].e = ml2[j + 1].e;
315                 }
316                 ml2[mp->totloop - 1].e = e;
317
318                 mp->loopstart += maxLoops;
319         }
320
321         /* adjust mirrored loop vertex and edge indices */
322         ml = result->mloop + maxLoops;
323         for (i = 0; i < maxLoops; i++, ml++) {
324                 ml->v += maxVerts;
325                 ml->e += maxEdges;
326         }
327
328         /* handle uvs,
329          * let tessface recalc handle updating the MTFace data */
330         if (mmd->flag & (MOD_MIR_MIRROR_U | MOD_MIR_MIRROR_V) || (is_zero_v2(mmd->uv_offset_copy) == false)) {
331                 const bool do_mirr_u = (mmd->flag & MOD_MIR_MIRROR_U) != 0;
332                 const bool do_mirr_v = (mmd->flag & MOD_MIR_MIRROR_V) != 0;
333
334                 const int totuv = CustomData_number_of_layers(&result->ldata, CD_MLOOPUV);
335
336                 for (a = 0; a < totuv; a++) {
337                         MLoopUV *dmloopuv = CustomData_get_layer_n(&result->ldata, CD_MLOOPUV, a);
338                         int j = maxLoops;
339                         dmloopuv += j; /* second set of loops only */
340                         for (; j-- > 0; dmloopuv++) {
341                                 if (do_mirr_u) dmloopuv->uv[0] = 1.0f - dmloopuv->uv[0] + mmd->uv_offset[0];
342                                 if (do_mirr_v) dmloopuv->uv[1] = 1.0f - dmloopuv->uv[1] + mmd->uv_offset[1];
343                                 dmloopuv->uv[0] += mmd->uv_offset_copy[0];
344                                 dmloopuv->uv[1] += mmd->uv_offset_copy[1];
345                         }
346                 }
347         }
348
349         /* handle vgroup stuff */
350         if ((mmd->flag & MOD_MIR_VGROUP) && CustomData_has_layer(&result->vdata, CD_MDEFORMVERT)) {
351                 MDeformVert *dvert = (MDeformVert *) CustomData_get_layer(&result->vdata, CD_MDEFORMVERT) + maxVerts;
352                 int *flip_map = NULL, flip_map_len = 0;
353
354                 flip_map = defgroup_flip_map(ob, &flip_map_len, false);
355
356                 if (flip_map) {
357                         for (i = 0; i < maxVerts; dvert++, i++) {
358                                 /* merged vertices get both groups, others get flipped */
359                                 if (do_vtargetmap && (vtargetmap[i] != -1))
360                                         defvert_flip_merged(dvert, flip_map, flip_map_len);
361                                 else
362                                         defvert_flip(dvert, flip_map, flip_map_len);
363                         }
364
365                         MEM_freeN(flip_map);
366                 }
367         }
368
369         if (do_vtargetmap) {
370                 /* slow - so only call if one or more merge verts are found,
371                  * users may leave this on and not realize there is nothing to merge - campbell */
372                 if (tot_vtargetmap) {
373                         result = BKE_mesh_merge_verts(result, vtargetmap, tot_vtargetmap, MESH_MERGE_VERTS_DUMP_IF_MAPPED);
374                 }
375                 MEM_freeN(vtargetmap);
376         }
377
378         if (mesh_bisect != NULL) {
379                 BKE_id_free(NULL, mesh_bisect);
380         }
381
382         return result;
383 }
384
385 static Mesh *mirrorModifier__doMirror(
386         MirrorModifierData *mmd, const ModifierEvalContext *ctx,
387         Object *ob, Mesh *mesh)
388 {
389         Mesh *result = mesh;
390
391         /* check which axes have been toggled and mirror accordingly */
392         if (mmd->flag & MOD_MIR_AXIS_X) {
393                 result = doMirrorOnAxis(mmd, ctx, ob, result, 0);
394         }
395         if (mmd->flag & MOD_MIR_AXIS_Y) {
396                 Mesh *tmp = result;
397                 result = doMirrorOnAxis(mmd, ctx, ob, result, 1);
398                 if (tmp != mesh) {
399                         /* free intermediate results */
400                         BKE_id_free(NULL, tmp);
401                 }
402         }
403         if (mmd->flag & MOD_MIR_AXIS_Z) {
404                 Mesh *tmp = result;
405                 result = doMirrorOnAxis(mmd, ctx, ob, result, 2);
406                 if (tmp != mesh) {
407                         /* free intermediate results */
408                         BKE_id_free(NULL, tmp);
409                 }
410         }
411
412         return result;
413 }
414
415 static Mesh *applyModifier(
416         ModifierData *md, const ModifierEvalContext *ctx,
417         Mesh *mesh)
418 {
419         Mesh *result;
420         MirrorModifierData *mmd = (MirrorModifierData *) md;
421
422         result = mirrorModifier__doMirror(mmd, ctx, ctx->object, mesh);
423
424         if (result != mesh) {
425                 result->runtime.cd_dirty_vert |= CD_MASK_NORMAL;
426         }
427         return result;
428 }
429
430
431 ModifierTypeInfo modifierType_Mirror = {
432         /* name */              "Mirror",
433         /* structName */        "MirrorModifierData",
434         /* structSize */        sizeof(MirrorModifierData),
435         /* type */              eModifierTypeType_Constructive,
436         /* flags */             eModifierTypeFlag_AcceptsMesh |
437                                 eModifierTypeFlag_SupportsMapping |
438                                 eModifierTypeFlag_SupportsEditmode |
439                                 eModifierTypeFlag_EnableInEditmode |
440                                 eModifierTypeFlag_AcceptsCVs |
441                                 /* this is only the case when 'MOD_MIR_VGROUP' is used */
442                                 eModifierTypeFlag_UsesPreview,
443
444         /* copyData */          modifier_copyData_generic,
445
446         /* deformVerts_DM */    NULL,
447         /* deformMatrices_DM */ NULL,
448         /* deformVertsEM_DM */  NULL,
449         /* deformMatricesEM_DM*/NULL,
450         /* applyModifier_DM */  NULL,
451
452         /* deformVerts */       NULL,
453         /* deformMatrices */    NULL,
454         /* deformVertsEM */     NULL,
455         /* deformMatricesEM */  NULL,
456         /* applyModifier */     applyModifier,
457
458         /* initData */          initData,
459         /* requiredDataMask */  NULL,
460         /* freeData */          NULL,
461         /* isDisabled */        NULL,
462         /* updateDepsgraph */   updateDepsgraph,
463         /* dependsOnTime */     NULL,
464         /* dependsOnNormals */  NULL,
465         /* foreachObjectLink */ foreachObjectLink,
466         /* foreachIDLink */     NULL,
467         /* foreachTexLink */    NULL,
468 };