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