added boolean type for bmesh operators, will make python wrapping clearer and also...
[blender.git] / source / blender / bmesh / operators / bmo_extrude.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 #include "MEM_guardedalloc.h"
24
25 #include "BLI_math.h"
26 #include "BLI_array.h"
27
28 #include "bmesh.h"
29
30 #include "bmesh_operators_private.h" /* own include */
31
32 #define EXT_INPUT 1
33 #define EXT_KEEP  2
34 #define EXT_DEL   4
35
36 #define VERT_MARK 1
37 #define EDGE_MARK 1
38 #define FACE_MARK 1
39 #define VERT_NONMAN 2
40 #define EDGE_NONMAN 2
41
42 void bmesh_extrude_face_indiv_exec(BMesh *bm, BMOperator *op)
43 {
44         BMOIter siter;
45         BMIter liter, liter2;
46         BMFace *f, *f2, *f3;
47         BMLoop *l, *l2, *l3, *l4, *l_tmp;
48         BMEdge **edges = NULL, *e, *laste;
49         BMVert *v, *lastv, *firstv;
50         BLI_array_declare(edges);
51         int i;
52
53         BMO_ITER(f, &siter, bm, op, "faces", BM_FACE) {
54                 BLI_array_empty(edges);
55                 i = 0;
56                 firstv = lastv = NULL;
57                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
58                         BLI_array_growone(edges);
59
60                         v = BM_vert_create(bm, l->v->co, l->v);
61
62                         if (lastv) {
63                                 e = BM_edge_create(bm, lastv, v, l->e, FALSE);
64                                 edges[i++] = e;
65                         }
66
67                         lastv = v;
68                         laste = l->e;
69                         if (!firstv) firstv = v;
70                 }
71
72                 BLI_array_growone(edges);
73                 e = BM_edge_create(bm, v, firstv, laste, FALSE);
74                 edges[i++] = e;
75
76                 BMO_elem_flag_enable(bm, f, EXT_DEL);
77
78                 f2 = BM_face_create_ngon(bm, firstv, BM_edge_other_vert(edges[0], firstv), edges, f->len, FALSE);
79                 if (!f2) {
80                         BMO_error_raise(bm, op, BMERR_MESH_ERROR, "Extrude failed; could not create face");
81                         BLI_array_free(edges);
82                         return;
83                 }
84                 
85                 BMO_elem_flag_enable(bm, f2, EXT_KEEP);
86                 BM_elem_attrs_copy(bm, bm, f, f2);
87
88                 l2 = BM_iter_new(&liter2, bm, BM_LOOPS_OF_FACE, f2);
89                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
90                         BM_elem_attrs_copy(bm, bm, l, l2);
91
92                         l3 = l->next;
93                         l4 = l2->next;
94
95                         f3 = BM_face_create_quad_tri(bm, l3->v, l4->v, l2->v, l->v, f, FALSE);
96
97                         l_tmp = BM_FACE_FIRST_LOOP(f3);
98
99                         BM_elem_attrs_copy(bm, bm, l->next, l_tmp);  l_tmp = l_tmp->next;
100                         BM_elem_attrs_copy(bm, bm, l->next, l_tmp);  l_tmp = l_tmp->next;
101                         BM_elem_attrs_copy(bm, bm, l, l_tmp);        l_tmp = l_tmp->next;
102                         BM_elem_attrs_copy(bm, bm, l, l_tmp);
103
104                         l2 = BM_iter_step(&liter2);
105                 }
106         }
107
108         BLI_array_free(edges);
109
110         BMO_op_callf(bm, "del geom=%ff context=%i", EXT_DEL, DEL_ONLYFACES);
111         BMO_slot_from_flag(bm, op, "faceout", EXT_KEEP, BM_FACE);
112 }
113
114 void bmesh_extrude_onlyedge_exec(BMesh *bm, BMOperator *op)
115 {
116         BMOIter siter;
117         BMOperator dupeop;
118         BMVert *v1, *v2, *v3, *v4;
119         BMEdge *e, *e2;
120         BMFace *f;
121         
122         BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) {
123                 BMO_elem_flag_enable(bm, e, EXT_INPUT);
124                 BMO_elem_flag_enable(bm, e->v1, EXT_INPUT);
125                 BMO_elem_flag_enable(bm, e->v2, EXT_INPUT);
126         }
127
128         BMO_op_initf(bm, &dupeop, "dupe geom=%fve", EXT_INPUT);
129         BMO_op_exec(bm, &dupeop);
130
131         e = BMO_iter_new(&siter, bm, &dupeop, "boundarymap", 0);
132         for ( ; e; e = BMO_iter_step(&siter)) {
133                 e2 = BMO_iter_map_value(&siter);
134                 e2 = *(BMEdge **)e2;
135
136                 if (e->l && e->v1 != e->l->v) {
137                         v1 = e->v1;
138                         v2 = e->v2;
139                         v3 = e2->v2;
140                         v4 = e2->v1;
141                 }
142                 else {
143                         v1 = e2->v1;
144                         v2 = e2->v2;
145                         v3 = e->v2;
146                         v4 = e->v1;
147                 }
148                 /* not sure what to do about example face, pass  NULL for now */
149                 f = BM_face_create_quad_tri(bm, v1, v2, v3, v4, NULL, FALSE);
150                 
151                 if (BMO_elem_flag_test(bm, e, EXT_INPUT))
152                         e = e2;
153                 
154                 BMO_elem_flag_enable(bm, f, EXT_KEEP);
155                 BMO_elem_flag_enable(bm, e, EXT_KEEP);
156                 BMO_elem_flag_enable(bm, e->v1, EXT_KEEP);
157                 BMO_elem_flag_enable(bm, e->v2, EXT_KEEP);
158                 
159         }
160
161         BMO_op_finish(bm, &dupeop);
162
163         BMO_slot_from_flag(bm, op, "geomout", EXT_KEEP, BM_ALL);
164 }
165
166 void extrude_vert_indiv_exec(BMesh *bm, BMOperator *op)
167 {
168         BMOIter siter;
169         BMVert *v, *dupev;
170         BMEdge *e;
171
172         v = BMO_iter_new(&siter, bm, op, "verts", BM_VERT);
173         for ( ; v; v = BMO_iter_step(&siter)) {
174                 dupev = BM_vert_create(bm, v->co, v);
175
176                 e = BM_edge_create(bm, v, dupev, NULL, FALSE);
177
178                 BMO_elem_flag_enable(bm, e, EXT_KEEP);
179                 BMO_elem_flag_enable(bm, dupev, EXT_KEEP);
180         }
181
182         BMO_slot_from_flag(bm, op, "vertout", EXT_KEEP, BM_VERT);
183         BMO_slot_from_flag(bm, op, "edgeout", EXT_KEEP, BM_EDGE);
184 }
185
186 void extrude_edge_context_exec(BMesh *bm, BMOperator *op)
187 {
188         BMOperator dupeop, delop;
189         BMOIter siter;
190         BMIter iter, fiter, viter;
191         BMEdge *e, *newedge;
192         BMLoop *l, *l2;
193         BMVert *verts[4], *v, *v2;
194         BMFace *f;
195         int rlen, found, fwd, delorig = 0;
196
197         /* initialize our sub-operators */
198         BMO_op_init(bm, &dupeop, "dupe");
199         
200         BMO_slot_buffer_flag_enable(bm, op, "edgefacein", EXT_INPUT, BM_EDGE|BM_FACE);
201         
202         /* if one flagged face is bordered by an unflagged face, then we delete
203          * original geometry unless caller explicitly asked to keep it. */
204         if (!BMO_slot_bool_get(op, "alwayskeeporig")) {
205                 BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
206                         if (!BMO_elem_flag_test(bm, e, EXT_INPUT)) continue;
207
208                         found = 0;
209                         f = BM_iter_new(&fiter, bm, BM_FACES_OF_EDGE, e);
210                         for (rlen = 0; f; f = BM_iter_step(&fiter), rlen++) {
211                                 if (!BMO_elem_flag_test(bm, f, EXT_INPUT)) {
212                                         found = 1;
213                                         delorig = 1;
214                                         break;
215                                 }
216                         }
217
218                         if (!found && (rlen > 1)) BMO_elem_flag_enable(bm, e, EXT_DEL);
219                 }
220         }
221
222         /* calculate verts to delet */
223         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
224                 found = 0;
225
226                 BM_ITER(e, &viter, bm, BM_EDGES_OF_VERT, v) {
227                         if (!BMO_elem_flag_test(bm, e, EXT_INPUT) || !BMO_elem_flag_test(bm, e, EXT_DEL)) {
228                                 found = 1;
229                                 break;
230                         }
231                 }
232                 
233                 BM_ITER(f, &viter, bm, BM_FACES_OF_VERT, v) {
234                         if (!BMO_elem_flag_test(bm, f, EXT_INPUT)) {
235                                 found = 1;
236                                 break;
237                         }
238                 }
239
240                 if (!found) {
241                         BMO_elem_flag_enable(bm, v, EXT_DEL);
242                 }
243         }
244         
245         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
246                 if (BMO_elem_flag_test(bm, f, EXT_INPUT))
247                         BMO_elem_flag_enable(bm, f, EXT_DEL);
248         }
249
250         if (delorig) {
251                 BMO_op_initf(bm, &delop, "del geom=%fvef context=%i",
252                              EXT_DEL, DEL_ONLYTAGGED);
253         }
254
255         BMO_slot_copy(op, &dupeop, "edgefacein", "geom");
256         BMO_op_exec(bm, &dupeop);
257
258         if (bm->act_face && BMO_elem_flag_test(bm, bm->act_face, EXT_INPUT))
259                 bm->act_face = BMO_slot_map_ptr_get(bm, &dupeop, "facemap", bm->act_face);
260
261         if (delorig) BMO_op_exec(bm, &delop);
262         
263         /* if not delorig, reverse loops of original face */
264         if (!delorig) {
265                 for (f = BM_iter_new(&iter, bm, BM_FACES_OF_MESH, NULL); f; f = BM_iter_step(&iter)) {
266                         if (BMO_elem_flag_test(bm, f, EXT_INPUT)) {
267                                 BM_face_normal_flip(bm, f);
268                         }
269                 }
270         }
271         
272         BMO_slot_copy(&dupeop, op, "newout", "geomout");
273         e = BMO_iter_new(&siter, bm, &dupeop, "boundarymap", 0);
274         for ( ; e; e = BMO_iter_step(&siter)) {
275                 if (BMO_slot_map_contains(bm, op, "exclude", e)) continue;
276
277                 newedge = BMO_iter_map_value(&siter);
278                 newedge = *(BMEdge **)newedge;
279                 if (!newedge) continue;
280
281                 /* orient loop to give same normal as a loop of newedge
282                  * if it exists (will be an extruded face),
283                  * else same normal as a loop of e, if it exists */
284                 if (!newedge->l)
285                         fwd = !e->l || !(e->l->v == e->v1);
286                 else
287                         fwd = (newedge->l->v == newedge->v1);
288
289                 
290                 if (fwd) {
291                         verts[0] = e->v1;
292                         verts[1] = e->v2;
293                         verts[2] = newedge->v2;
294                         verts[3] = newedge->v1;
295                 }
296                 else {
297                         verts[3] = e->v1;
298                         verts[2] = e->v2;
299                         verts[1] = newedge->v2;
300                         verts[0] = newedge->v1;
301                 }
302
303                 /* not sure what to do about example face, pass NULL for now */
304                 f = BM_face_create_quad_tri_v(bm, verts, 4, NULL, FALSE);
305
306                 /* copy attribute */
307                 l = BM_iter_new(&iter, bm, BM_LOOPS_OF_FACE, f);
308                 for ( ; l; l = BM_iter_step(&iter)) {
309                         if (l->e != e && l->e != newedge) continue;
310                         l2 = l->radial_next;
311                         
312                         if (l2 == l) {
313                                 l2 = newedge->l;
314                                 BM_elem_attrs_copy(bm, bm, l2->f, l->f);
315
316                                 BM_elem_attrs_copy(bm, bm, l2, l);
317                                 l2 = l2->next;
318                                 l = l->next;
319                                 BM_elem_attrs_copy(bm, bm, l2, l);
320                         }
321                         else {
322                                 BM_elem_attrs_copy(bm, bm, l2->f, l->f);
323
324                                 /* copy dat */
325                                 if (l2->v == l->v) {
326                                         BM_elem_attrs_copy(bm, bm, l2, l);
327                                         l2 = l2->next;
328                                         l = l->next;
329                                         BM_elem_attrs_copy(bm, bm, l2, l);
330                                 }
331                                 else {
332                                         l2 = l2->next;
333                                         BM_elem_attrs_copy(bm, bm, l2, l);
334                                         l2 = l2->prev;
335                                         l = l->next;
336                                         BM_elem_attrs_copy(bm, bm, l2, l);
337                                 }
338                         }
339                 }
340         }
341
342         /* link isolated vert */
343         v = BMO_iter_new(&siter, bm, &dupeop, "isovertmap", 0);
344         for ( ; v; v = BMO_iter_step(&siter)) {
345                 v2 = *((void **)BMO_iter_map_value(&siter));
346                 BM_edge_create(bm, v, v2, v->e, TRUE);
347         }
348
349         /* cleanu */
350         if (delorig) BMO_op_finish(bm, &delop);
351         BMO_op_finish(bm, &dupeop);
352 }
353
354 /*
355  * Compute higher-quality vertex normals used by solidify.
356  * Only considers geometry in the marked solidify region.
357  * Note that this does not work so well for non-manifold
358  * regions.
359  */
360 static void calc_solidify_normals(BMesh *bm)
361 {
362         BMIter viter, eiter, fiter;
363         BMVert *v;
364         BMEdge *e;
365         BMFace *f, *f1, *f2;
366         float edge_normal[3];
367         int i;
368
369         /* can't use BM_edge_face_count because we need to count only marked faces */
370         int *edge_face_count = MEM_callocN(sizeof(int) * bm->totedge, __func__);
371
372         BM_ITER(v, &viter, bm, BM_VERTS_OF_MESH, NULL) {
373                 BM_elem_flag_enable(v, BM_ELEM_TAG);
374         }
375
376         BM_mesh_elem_index_ensure(bm, BM_EDGE);
377
378         BM_ITER(f, &fiter, bm, BM_FACES_OF_MESH, NULL) {
379                 if (!BMO_elem_flag_test(bm, f, FACE_MARK)) {
380                         continue;
381                 }
382
383                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_FACE, f) {
384
385                         /* And mark all edges and vertices on the
386                          * marked faces */
387                         BMO_elem_flag_enable(bm, e, EDGE_MARK);
388                         BMO_elem_flag_enable(bm, e->v1, VERT_MARK);
389                         BMO_elem_flag_enable(bm, e->v2, VERT_MARK);
390                         edge_face_count[BM_elem_index_get(e)]++;
391                 }
392         }
393
394         BM_ITER(e, &eiter, bm, BM_EDGES_OF_MESH, NULL) {
395                 if (!BMO_elem_flag_test(bm, e, EDGE_MARK)) {
396                         continue;
397                 }
398
399                 i = edge_face_count[BM_elem_index_get(e)]++;
400
401                 if (i == 0 || i > 2) {
402                         /* Edge & vertices are non-manifold even when considering
403                          * only marked faces */
404                         BMO_elem_flag_enable(bm, e, EDGE_NONMAN);
405                         BMO_elem_flag_enable(bm, e->v1, VERT_NONMAN);
406                         BMO_elem_flag_enable(bm, e->v2, VERT_NONMAN);
407                 }
408         }
409         MEM_freeN(edge_face_count);
410         edge_face_count = NULL; /* dont re-use */
411
412         BM_ITER(v, &viter, bm, BM_VERTS_OF_MESH, NULL) {
413                 if (!BM_vert_is_manifold(bm, v)) {
414                         BMO_elem_flag_enable(bm, v, VERT_NONMAN);
415                         continue;
416                 }
417
418                 if (BMO_elem_flag_test(bm, v, VERT_MARK)) {
419                         zero_v3(v->no);
420                 }
421         }
422
423         BM_ITER(e, &eiter, bm, BM_EDGES_OF_MESH, NULL) {
424
425                 /* If the edge is not part of a the solidify region
426                  * its normal should not be considered */
427                 if (!BMO_elem_flag_test(bm, e, EDGE_MARK)) {
428                         continue;
429                 }
430
431                 /* If the edge joins more than two marked faces high
432                  * quality normal computation won't work */
433                 if (BMO_elem_flag_test(bm, e, EDGE_NONMAN)) {
434                         continue;
435                 }
436
437                 f1 = f2 = NULL;
438
439                 BM_ITER(f, &fiter, bm, BM_FACES_OF_EDGE, e) {
440                         if (BMO_elem_flag_test(bm, f, FACE_MARK)) {
441                                 if (f1 == NULL) {
442                                         f1 = f;
443                                 }
444                                 else {
445                                         BLI_assert(f2 == NULL);
446                                         f2 = f;
447                                 }
448                         }
449                 }
450
451                 BLI_assert(f1 != NULL);
452
453                 if (f2 != NULL) {
454                         const float angle = angle_normalized_v3v3(f1->no, f2->no);
455
456                         if (angle > 0.0f) {
457                                 /* two faces using this edge, calculate the edge normal
458                                  * using the angle between the faces as a weighting */
459                                 add_v3_v3v3(edge_normal, f1->no, f2->no);
460                                 normalize_v3(edge_normal);
461                                 mul_v3_fl(edge_normal, angle);
462                         }
463                         else {
464                                 /* can't do anything useful here!
465                                  * Set the face index for a vert incase it gets a zero normal */
466                                 BM_elem_flag_disable(e->v1, BM_ELEM_TAG);
467                                 BM_elem_flag_disable(e->v2, BM_ELEM_TAG);
468                                 continue;
469                         }
470                 }
471                 else {
472                         /* only one face attached to that edge */
473                         /* an edge without another attached- the weight on this is
474                          * undefined, M_PI / 2 is 90d in radians and that seems good enough */
475                         copy_v3_v3(edge_normal, f1->no);
476                         mul_v3_fl(edge_normal, M_PI / 2);
477                 }
478
479                 add_v3_v3(e->v1->no, edge_normal);
480                 add_v3_v3(e->v2->no, edge_normal);
481         }
482
483         /* normalize accumulated vertex normal */
484         BM_ITER(v, &viter, bm, BM_VERTS_OF_MESH, NULL) {
485                 if (!BMO_elem_flag_test(bm, v, VERT_MARK)) {
486                         continue;
487                 }
488
489                 if (BMO_elem_flag_test(bm, v, VERT_NONMAN)) {
490                         /* use standard normals for vertices connected to non-manifold edges */
491                         BM_vert_normal_update(bm, v);
492                 }
493                 else if (normalize_v3(v->no) == 0.0f && !BM_elem_flag_test(v, BM_ELEM_TAG)) {
494                         /* exceptional case, totally flat. use the normal
495                          * of any marked face around the vertex */
496                         BM_ITER(f, &fiter, bm, BM_FACES_OF_VERT, v) {
497                                 if (BMO_elem_flag_test(bm, f, FACE_MARK)) {
498                                         break;
499                                 }
500                         }
501                         copy_v3_v3(v->no, f->no);
502                 }
503         }
504 }
505
506 static void solidify_add_thickness(BMesh *bm, float dist)
507 {
508         BMFace *f;
509         BMVert *v;
510         BMLoop *l;
511         BMIter iter, loopIter;
512         float *vert_angles = MEM_callocN(sizeof(float) * bm->totvert * 2, "solidify"); /* 2 in 1 */
513         float *vert_accum = vert_angles + bm->totvert;
514         float angle;
515         int i, index;
516         float maxdist = dist * sqrtf(3.0f);
517
518         /* array for passing verts to angle_poly_v3 */
519         float **verts = NULL;
520         BLI_array_staticdeclare(verts, BM_NGON_STACK_SIZE);
521         /* array for receiving angles from angle_poly_v3 */
522         float *angles = NULL;
523         BLI_array_staticdeclare(angles, BM_NGON_STACK_SIZE);
524
525         BM_mesh_elem_index_ensure(bm, BM_VERT);
526
527         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
528                 if (!BMO_elem_flag_test(bm, f, FACE_MARK)) {
529                         continue;
530                 }
531
532                 BM_ITER(l, &loopIter, bm, BM_LOOPS_OF_FACE, f) {
533                         BLI_array_append(verts, l->v->co);
534                         BLI_array_growone(angles);
535                 }
536
537                 angle_poly_v3(angles, (const float **)verts, f->len);
538
539                 i = 0;
540                 BM_ITER(l, &loopIter, bm, BM_LOOPS_OF_FACE, f) {
541                         v = l->v;
542                         index = BM_elem_index_get(v);
543                         angle = angles[i];
544                         vert_accum[index] += angle;
545                         vert_angles[index] += shell_angle_to_dist(angle_normalized_v3v3(v->no, f->no)) * angle;
546                         i++;
547                 }
548
549                 BLI_array_empty(verts);
550                 BLI_array_empty(angles);
551         }
552
553         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
554                 index = BM_elem_index_get(v);
555                 if (vert_accum[index]) { /* zero if unselected */
556                         float vdist = MIN2(maxdist, dist * vert_angles[index] / vert_accum[index]);
557                         madd_v3_v3fl(v->co, v->no, vdist);
558                 }
559         }
560
561         MEM_freeN(vert_angles);
562 }
563
564 void bmesh_solidify_face_region_exec(BMesh *bm, BMOperator *op)
565 {
566         BMOperator extrudeop;
567         BMOperator reverseop;
568         float thickness;
569
570         thickness = BMO_slot_float_get(op, "thickness");
571
572         /* Flip original faces (so the shell is extruded inward) */
573         BMO_op_init(bm, &reverseop, "reversefaces");
574         BMO_slot_copy(op, &reverseop, "geom", "faces");
575         BMO_op_exec(bm, &reverseop);
576         BMO_op_finish(bm, &reverseop);
577
578         /* Extrude the region */
579         BMO_op_initf(bm, &extrudeop, "extrudefaceregion alwayskeeporig=%b", TRUE);
580         BMO_slot_copy(op, &extrudeop, "geom", "edgefacein");
581         BMO_op_exec(bm, &extrudeop);
582
583         /* Push the verts of the extruded faces inward to create thickness */
584         BMO_slot_buffer_flag_enable(bm, &extrudeop, "geomout", FACE_MARK, BM_FACE);
585         calc_solidify_normals(bm);
586         solidify_add_thickness(bm, thickness);
587
588         BMO_slot_copy(&extrudeop, op, "geomout", "geomout");
589
590         BMO_op_finish(bm, &extrudeop);
591 }