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