Fix T53811: "bmesh.ops.split" crash
[blender-staging.git] / source / blender / bmesh / operators / bmo_dupe.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  * Contributor(s): Joseph Eagar.
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/bmesh/operators/bmo_dupe.c
24  *  \ingroup bmesh
25  *
26  * Duplicate, Split, Split operators.
27  */
28
29 #include "BLI_math.h"
30 #include "BLI_alloca.h"
31
32 #include "bmesh.h"
33
34 #include "intern/bmesh_operators_private.h" /* own include */
35
36 /* local flag define */
37 #define DUPE_INPUT      1 /* input from operator */
38 #define DUPE_NEW        2
39 #define DUPE_DONE       4
40 // #define DUPE_MAPPED     8 // UNUSED
41
42 /**
43  * COPY VERTEX
44  *
45  * Copy an existing vertex from one bmesh to another.
46  */
47 static BMVert *bmo_vert_copy(
48         BMOperator *op,
49         BMOpSlot *slot_vertmap_out,
50         BMesh *bm_dst, BMesh *bm_src, BMVert *v_src, GHash *vhash)
51 {
52         BMVert *v_dst;
53
54         /* Create a new vertex */
55         v_dst = BM_vert_create(bm_dst, v_src->co, NULL, BM_CREATE_SKIP_CD);
56         BMO_slot_map_elem_insert(op, slot_vertmap_out, v_src, v_dst);
57         BMO_slot_map_elem_insert(op, slot_vertmap_out, v_dst, v_src);
58
59         /* Insert new vertex into the vert hash */
60         BLI_ghash_insert(vhash, v_src, v_dst);
61
62         /* Copy attributes */
63         BM_elem_attrs_copy(bm_src, bm_dst, v_src, v_dst);
64
65         /* Mark the vert for output */
66         BMO_vert_flag_enable(bm_dst, v_dst, DUPE_NEW);
67         
68         return v_dst;
69 }
70
71 /**
72  * COPY EDGE
73  *
74  * Copy an existing edge from one bmesh to another.
75  */
76 static BMEdge *bmo_edge_copy(
77         BMOperator *op,
78         BMOpSlot *slot_edgemap_out,
79         BMOpSlot *slot_boundarymap_out,
80         BMesh *bm_dst, BMesh *bm_src,
81         BMEdge *e_src,
82         GHash *vhash, GHash *ehash)
83 {
84         BMEdge *e_dst;
85         BMVert *e_dst_v1, *e_dst_v2;
86         uint rlen;
87
88         /* see if any of the neighboring faces are
89          * not being duplicated.  in that case,
90          * add it to the new/old map. */
91         /* lookup edge */
92         rlen = 0;
93         if (e_src->l) {
94                 BMLoop *l_iter_src, *l_first_src;
95                 l_iter_src = l_first_src = e_src->l;
96                 do {
97                         if (BMO_face_flag_test(bm_src, l_iter_src->f, DUPE_INPUT)) {
98                                 rlen++;
99                         }
100                 } while ((l_iter_src = l_iter_src->radial_next) != l_first_src);
101         }
102
103         /* Lookup v1 and v2 */
104         e_dst_v1 = BLI_ghash_lookup(vhash, e_src->v1);
105         e_dst_v2 = BLI_ghash_lookup(vhash, e_src->v2);
106         
107         /* Create a new edge */
108         e_dst = BM_edge_create(bm_dst, e_dst_v1, e_dst_v2, NULL, BM_CREATE_SKIP_CD);
109         BMO_slot_map_elem_insert(op, slot_edgemap_out, e_src, e_dst);
110         BMO_slot_map_elem_insert(op, slot_edgemap_out, e_dst, e_src);
111
112         /* add to new/old edge map if necassary */
113         if (rlen < 2) {
114                 /* not sure what non-manifold cases of greater than three
115                  * radial should do. */
116                 BMO_slot_map_elem_insert(op, slot_boundarymap_out, e_src, e_dst);
117         }
118
119         /* Insert new edge into the edge hash */
120         BLI_ghash_insert(ehash, e_src, e_dst);
121
122         /* Copy attributes */
123         BM_elem_attrs_copy(bm_src, bm_dst, e_src, e_dst);
124
125         /* Mark the edge for output */
126         BMO_edge_flag_enable(bm_dst, e_dst, DUPE_NEW);
127         
128         return e_dst;
129 }
130
131 /**
132  * COPY FACE
133  *
134  * Copy an existing face from one bmesh to another.
135  */
136 static BMFace *bmo_face_copy(
137         BMOperator *op,
138         BMOpSlot *slot_facemap_out,
139         BMesh *bm_dst, BMesh *bm_src,
140         BMFace *f_src,
141         GHash *vhash, GHash *ehash)
142 {
143         BMFace *f_dst;
144         BMVert **vtar = BLI_array_alloca(vtar, f_src->len);
145         BMEdge **edar = BLI_array_alloca(edar, f_src->len);
146         BMLoop *l_iter_src, *l_iter_dst, *l_first_src;
147         int i;
148
149         l_first_src = BM_FACE_FIRST_LOOP(f_src);
150
151         /* lookup edge */
152         l_iter_src = l_first_src;
153         i = 0;
154         do {
155                 vtar[i] = BLI_ghash_lookup(vhash, l_iter_src->v);
156                 edar[i] = BLI_ghash_lookup(ehash, l_iter_src->e);
157                 i++;
158         } while ((l_iter_src = l_iter_src->next) != l_first_src);
159
160         /* create new face */
161         f_dst = BM_face_create(bm_dst, vtar, edar, f_src->len, NULL, BM_CREATE_SKIP_CD);
162         BMO_slot_map_elem_insert(op, slot_facemap_out, f_src, f_dst);
163         BMO_slot_map_elem_insert(op, slot_facemap_out, f_dst, f_src);
164
165         /* Copy attributes */
166         BM_elem_attrs_copy(bm_src, bm_dst, f_src, f_dst);
167         
168         /* copy per-loop custom data */
169         l_iter_src = l_first_src;
170         l_iter_dst = BM_FACE_FIRST_LOOP(f_dst);
171         do {
172                 BM_elem_attrs_copy(bm_src, bm_dst, l_iter_src, l_iter_dst);
173         } while ((void)
174                  (l_iter_dst = l_iter_dst->next),
175                  (l_iter_src = l_iter_src->next) != l_first_src);
176
177         /* Mark the face for output */
178         BMO_face_flag_enable(bm_dst, f_dst, DUPE_NEW);
179
180         return f_dst;
181 }
182
183 /**
184  * COPY MESH
185  *
186  * Internal Copy function.
187  */
188 static void bmo_mesh_copy(BMOperator *op, BMesh *bm_dst, BMesh *bm_src)
189 {
190         const bool use_select_history = BMO_slot_bool_get(op->slots_in, "use_select_history");
191
192         BMVert *v = NULL, *v2;
193         BMEdge *e = NULL;
194         BMFace *f = NULL;
195         
196         BMIter viter, eiter, fiter;
197         GHash *vhash, *ehash;
198
199         BMOpSlot *slot_boundary_map_out = BMO_slot_get(op->slots_out, "boundary_map.out");
200         BMOpSlot *slot_isovert_map_out  = BMO_slot_get(op->slots_out, "isovert_map.out");
201
202         BMOpSlot *slot_vert_map_out = BMO_slot_get(op->slots_out, "vert_map.out");
203         BMOpSlot *slot_edge_map_out = BMO_slot_get(op->slots_out, "edge_map.out");
204         BMOpSlot *slot_face_map_out = BMO_slot_get(op->slots_out, "face_map.out");
205
206         /* initialize pointer hashes */
207         vhash = BLI_ghash_ptr_new("bmesh dupeops v");
208         ehash = BLI_ghash_ptr_new("bmesh dupeops e");
209
210         /* duplicate flagged vertices */
211         BM_ITER_MESH (v, &viter, bm_src, BM_VERTS_OF_MESH) {
212                 if (BMO_vert_flag_test(bm_src, v, DUPE_INPUT) &&
213                     BMO_vert_flag_test(bm_src, v, DUPE_DONE) == false)
214                 {
215                         BMIter iter;
216                         bool isolated = true;
217
218                         v2 = bmo_vert_copy(op, slot_vert_map_out, bm_dst, bm_src, v, vhash);
219
220                         BM_ITER_ELEM (f, &iter, v, BM_FACES_OF_VERT) {
221                                 if (BMO_face_flag_test(bm_src, f, DUPE_INPUT)) {
222                                         isolated = false;
223                                         break;
224                                 }
225                         }
226
227                         if (isolated) {
228                                 BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
229                                         if (BMO_edge_flag_test(bm_src, e, DUPE_INPUT)) {
230                                                 isolated = false;
231                                                 break;
232                                         }
233                                 }
234                         }
235
236                         if (isolated) {
237                                 BMO_slot_map_elem_insert(op, slot_isovert_map_out, v, v2);
238                         }
239
240                         BMO_vert_flag_enable(bm_src, v, DUPE_DONE);
241                 }
242         }
243
244         /* now we dupe all the edges */
245         BM_ITER_MESH (e, &eiter, bm_src, BM_EDGES_OF_MESH) {
246                 if (BMO_edge_flag_test(bm_src, e, DUPE_INPUT) &&
247                     BMO_edge_flag_test(bm_src, e, DUPE_DONE) == false)
248                 {
249                         /* make sure that verts are copied */
250                         if (!BMO_vert_flag_test(bm_src, e->v1, DUPE_DONE)) {
251                                 bmo_vert_copy(op, slot_vert_map_out, bm_dst, bm_src, e->v1, vhash);
252                                 BMO_vert_flag_enable(bm_src, e->v1, DUPE_DONE);
253                         }
254                         if (!BMO_vert_flag_test(bm_src, e->v2, DUPE_DONE)) {
255                                 bmo_vert_copy(op, slot_vert_map_out, bm_dst, bm_src, e->v2, vhash);
256                                 BMO_vert_flag_enable(bm_src, e->v2, DUPE_DONE);
257                         }
258                         /* now copy the actual edge */
259                         bmo_edge_copy(op, slot_edge_map_out, slot_boundary_map_out,
260                                       bm_dst, bm_src, e, vhash, ehash);
261                         BMO_edge_flag_enable(bm_src, e, DUPE_DONE);
262                 }
263         }
264
265         /* first we dupe all flagged faces and their elements from source */
266         BM_ITER_MESH (f, &fiter, bm_src, BM_FACES_OF_MESH) {
267                 if (BMO_face_flag_test(bm_src, f, DUPE_INPUT)) {
268                         /* vertex pass */
269                         BM_ITER_ELEM (v, &viter, f, BM_VERTS_OF_FACE) {
270                                 if (!BMO_vert_flag_test(bm_src, v, DUPE_DONE)) {
271                                         bmo_vert_copy(op, slot_vert_map_out, bm_dst, bm_src, v, vhash);
272                                         BMO_vert_flag_enable(bm_src, v, DUPE_DONE);
273                                 }
274                         }
275
276                         /* edge pass */
277                         BM_ITER_ELEM (e, &eiter, f, BM_EDGES_OF_FACE) {
278                                 if (!BMO_edge_flag_test(bm_src, e, DUPE_DONE)) {
279                                         bmo_edge_copy(op, slot_edge_map_out, slot_boundary_map_out,
280                                                       bm_dst, bm_src, e, vhash, ehash);
281                                         BMO_edge_flag_enable(bm_src, e, DUPE_DONE);
282                                 }
283                         }
284
285                         bmo_face_copy(op, slot_face_map_out, bm_dst, bm_src, f, vhash, ehash);
286                         BMO_face_flag_enable(bm_src, f, DUPE_DONE);
287                 }
288         }
289         
290         /* free pointer hashes */
291         BLI_ghash_free(vhash, NULL, NULL);
292         BLI_ghash_free(ehash, NULL, NULL);
293
294         if (use_select_history) {
295                 BLI_assert(bm_src == bm_dst);
296                 BMO_mesh_selected_remap(
297                         bm_dst,
298                         slot_vert_map_out,
299                         slot_edge_map_out,
300                         slot_face_map_out,
301                         false);
302         }
303 }
304
305 /**
306  * Duplicate Operator
307  *
308  * Duplicates verts, edges and faces of a mesh.
309  *
310  * INPUT SLOTS:
311  *
312  * BMOP_DUPE_VINPUT: Buffer containing pointers to mesh vertices to be duplicated
313  * BMOP_DUPE_EINPUT: Buffer containing pointers to mesh edges to be duplicated
314  * BMOP_DUPE_FINPUT: Buffer containing pointers to mesh faces to be duplicated
315  *
316  * OUTPUT SLOTS:
317  *
318  * BMOP_DUPE_VORIGINAL: Buffer containing pointers to the original mesh vertices
319  * BMOP_DUPE_EORIGINAL: Buffer containing pointers to the original mesh edges
320  * BMOP_DUPE_FORIGINAL: Buffer containing pointers to the original mesh faces
321  * BMOP_DUPE_VNEW: Buffer containing pointers to the new mesh vertices
322  * BMOP_DUPE_ENEW: Buffer containing pointers to the new mesh edges
323  * BMOP_DUPE_FNEW: Buffer containing pointers to the new mesh faces
324  */
325 void bmo_duplicate_exec(BMesh *bm, BMOperator *op)
326 {
327         BMOperator *dupeop = op;
328         BMesh *bm_dst = BMO_slot_ptr_get(op->slots_in, "dest");
329         
330         if (!bm_dst)
331                 bm_dst = bm;
332
333         /* flag input */
334         BMO_slot_buffer_flag_enable(bm, dupeop->slots_in, "geom", BM_ALL_NOLOOP, DUPE_INPUT);
335
336         /* use the internal copy function */
337         bmo_mesh_copy(dupeop, bm_dst, bm);
338         
339         /* Output */
340         /* First copy the input buffers to output buffers - original data */
341         BMO_slot_copy(dupeop, slots_in,  "geom",
342                       dupeop, slots_out, "geom_orig.out");
343
344         /* Now alloc the new output buffers */
345         BMO_slot_buffer_from_enabled_flag(bm, dupeop, dupeop->slots_out, "geom.out", BM_ALL_NOLOOP, DUPE_NEW);
346 }
347
348 #if 0 /* UNUSED */
349 /* executes the duplicate operation, feeding elements of
350  * type flag etypeflag and header flag flag to it.  note,
351  * to get more useful information (such as the mapping from
352  * original to new elements) you should run the dupe op manually */
353 void BMO_dupe_from_flag(BMesh *bm, int htype, const char hflag)
354 {
355         BMOperator dupeop;
356
357         BMO_op_init(bm, &dupeop, "duplicate");
358         BMO_slot_buffer_from_enabled_hflag(bm, &dupeop, "geom", htype, hflag);
359
360         BMO_op_exec(bm, &dupeop);
361         BMO_op_finish(bm, &dupeop);
362 }
363 #endif
364
365 /**
366  * Split Operator
367  *
368  * Duplicates verts, edges and faces of a mesh but also deletes the originals.
369  *
370  * INPUT SLOTS:
371  *
372  * BMOP_DUPE_VINPUT: Buffer containing pointers to mesh vertices to be split
373  * BMOP_DUPE_EINPUT: Buffer containing pointers to mesh edges to be split
374  * BMOP_DUPE_FINPUT: Buffer containing pointers to mesh faces to be split
375  *
376  * OUTPUT SLOTS:
377  *
378  * BMOP_DUPE_VOUTPUT: Buffer containing pointers to the split mesh vertices
379  * BMOP_DUPE_EOUTPUT: Buffer containing pointers to the split mesh edges
380  * BMOP_DUPE_FOUTPUT: Buffer containing pointers to the split mesh faces
381  *
382  * \note Lower level uses of this operator may want to use #BM_mesh_separate_faces
383  * Since it's faster for the 'use_only_faces' case.
384  *
385  */
386 void bmo_split_exec(BMesh *bm, BMOperator *op)
387 {
388 #define SPLIT_INPUT 1
389
390         BMOperator *splitop = op;
391         BMOperator dupeop;
392         const bool use_only_faces = BMO_slot_bool_get(op->slots_in, "use_only_faces");
393
394         /* initialize our sub-operator */
395         BMO_op_init(bm, &dupeop, op->flag, "duplicate");
396         
397         BMO_slot_copy(splitop, slots_in, "geom",
398                       &dupeop, slots_in, "geom");
399         BMO_op_exec(bm, &dupeop);
400         
401         BMO_slot_buffer_flag_enable(bm, splitop->slots_in, "geom", BM_ALL_NOLOOP, SPLIT_INPUT);
402
403         if (use_only_faces) {
404                 BMVert *v;
405                 BMEdge *e;
406                 BMFace *f;
407                 BMIter iter, iter2;
408
409                 /* make sure to remove edges and verts we don't need */
410                 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
411                         bool found = false;
412                         BM_ITER_ELEM (f, &iter2, e, BM_FACES_OF_EDGE) {
413                                 if (!BMO_face_flag_test(bm, f, SPLIT_INPUT)) {
414                                         found = true;
415                                         break;
416                                 }
417                         }
418                         if (found == false) {
419                                 BMO_edge_flag_enable(bm, e, SPLIT_INPUT);
420                         }
421                 }
422
423                 BM_ITER_MESH (v, &iter, bm,  BM_VERTS_OF_MESH) {
424                         bool found = false;
425                         BM_ITER_ELEM (e, &iter2, v, BM_EDGES_OF_VERT) {
426                                 if (!BMO_edge_flag_test(bm, e, SPLIT_INPUT)) {
427                                         found = true;
428                                         break;
429                                 }
430                         }
431                         if (found == false) {
432                                 BMO_vert_flag_enable(bm, v, SPLIT_INPUT);
433                         }
434                 }
435         }
436
437         /* connect outputs of dupe to delete, exluding keep geometry */
438         BMO_mesh_delete_oflag_context(bm, SPLIT_INPUT, DEL_FACES);
439
440         /* now we make our outputs by copying the dupe output */
441         BMO_slot_copy(&dupeop, slots_out, "geom.out",
442                       splitop, slots_out, "geom.out");
443
444         /* cleanup */
445         BMO_op_finish(bm, &dupeop);
446
447 #undef SPLIT_INPUT
448 }
449
450
451 void bmo_delete_exec(BMesh *bm, BMOperator *op)
452 {
453 #define DEL_INPUT 1
454
455         BMOperator *delop = op;
456
457         /* Mark Buffer */
458         BMO_slot_buffer_flag_enable(bm, delop->slots_in, "geom", BM_ALL_NOLOOP, DEL_INPUT);
459
460         BMO_mesh_delete_oflag_context(bm, DEL_INPUT, BMO_slot_int_get(op->slots_in, "context"));
461
462 #undef DEL_INPUT
463 }
464
465 /**
466  * Spin Operator
467  *
468  * Extrude or duplicate geometry a number of times,
469  * rotating and possibly translating after each step
470  */
471 void bmo_spin_exec(BMesh *bm, BMOperator *op)
472 {
473         BMOperator dupop, extop;
474         float cent[3], dvec[3];
475         float axis[3];
476         float rmat[3][3];
477         float phi;
478         int steps, do_dupli, a;
479         bool use_dvec;
480
481         BMO_slot_vec_get(op->slots_in, "cent", cent);
482         BMO_slot_vec_get(op->slots_in, "axis", axis);
483         normalize_v3(axis);
484         BMO_slot_vec_get(op->slots_in, "dvec", dvec);
485         use_dvec = !is_zero_v3(dvec);
486         steps    = BMO_slot_int_get(op->slots_in,   "steps");
487         phi      = BMO_slot_float_get(op->slots_in, "angle") / steps;
488         do_dupli = BMO_slot_bool_get(op->slots_in,  "use_duplicate");
489
490         axis_angle_normalized_to_mat3(rmat, axis, phi);
491
492         BMO_slot_copy(op, slots_in,  "geom",
493                       op, slots_out, "geom_last.out");
494         for (a = 0; a < steps; a++) {
495                 if (do_dupli) {
496                         BMO_op_initf(bm, &dupop, op->flag, "duplicate geom=%S", op, "geom_last.out");
497                         BMO_op_exec(bm, &dupop);
498                         BMO_op_callf(bm, op->flag,
499                                      "rotate cent=%v matrix=%m3 space=%s verts=%S",
500                                      cent, rmat, op, "space", &dupop, "geom.out");
501                         BMO_slot_copy(&dupop, slots_out, "geom.out",
502                                       op,     slots_out, "geom_last.out");
503                         BMO_op_finish(bm, &dupop);
504                 }
505                 else {
506                         BMO_op_initf(bm, &extop, op->flag, "extrude_face_region geom=%S",
507                                      op, "geom_last.out");
508                         BMO_op_exec(bm, &extop);
509                         BMO_op_callf(bm, op->flag,
510                                      "rotate cent=%v matrix=%m3 space=%s verts=%S",
511                                      cent, rmat, op, "space", &extop, "geom.out");
512                         BMO_slot_copy(&extop, slots_out, "geom.out",
513                                       op,     slots_out, "geom_last.out");
514                         BMO_op_finish(bm, &extop);
515                 }
516
517                 if (use_dvec) {
518                         mul_m3_v3(rmat, dvec);
519                         BMO_op_callf(bm, op->flag,
520                                      "translate vec=%v space=%s verts=%S",
521                                      dvec, op, "space", op, "geom_last.out");
522                 }
523         }
524 }