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