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