replace unhelpfully named `eck!` and `eek!` error prints, also some minor changes...
[blender.git] / source / blender / bmesh / operators / bevel.c
1 #include "MEM_guardedalloc.h"
2
3 #include "BLI_utildefines.h"
4 #include "BLI_ghash.h"
5 #include "BLI_memarena.h"
6 #include "BLI_blenlib.h"
7 #include "BLI_array.h"
8 #include "BLI_math.h"
9 #include "BLI_array.h"
10 #include "BLI_utildefines.h"
11 #include "BLI_smallhash.h"
12
13 #include "bmesh.h"
14 #include "bmesh_operators_private.h"
15
16 #define BEVEL_FLAG      1
17 #define BEVEL_DEL       2
18 #define FACE_NEW        4
19 #define EDGE_OLD        8
20 #define FACE_OLD        16
21 #define FACE_DONE       32
22 #define VERT_OLD        64
23 #define FACE_SPAN       128
24 #define FACE_HOLE       256
25
26 typedef struct LoopTag {
27         BMVert *newv;
28 } LoopTag;
29
30 typedef struct EdgeTag {
31         BMVert *newv1, *newv2;
32 } EdgeTag;
33
34 static void calc_corner_co(BMesh *bm, BMLoop *l, float *co, float fac)
35 {
36         float  no[3], /*tan[3]*,*/ vec1[3], vec2[3], v1[3], v2[3], v3[3], v4[3];
37         /*float p1[3], p2[3], w[3];
38         float l1, l2;*/
39         int /*ret,*/ inv=0;
40         
41         if (l->f->len > 2) {
42                 copy_v3_v3(v1, l->prev->v->co);
43                 copy_v3_v3(v2, l->v->co);
44                 copy_v3_v3(v3, l->v->co);
45                 copy_v3_v3(v4, l->next->v->co);
46         } else {
47                 BMIter iter;
48                 BMLoop *l2;
49                 float up[3] = {0.0f, 0.0f, 1.0f};
50                 
51                 copy_v3_v3(v1, l->prev->v->co);
52                 copy_v3_v3(v2, l->v->co);
53                 copy_v3_v3(v3, l->v->co);
54                 
55                 BM_ITER(l2, &iter, bm, BM_LOOPS_OF_VERT, l->v) {
56                         if (l2->f != l->f) {
57                                 copy_v3_v3(v4, BM_OtherEdgeVert(l2->e, l2->next->v)->co);
58                                 break;
59                         }
60                 }
61                 
62                 sub_v3_v3v3(vec1, v1, v2);
63                 sub_v3_v3v3(vec2, v4, v3);
64
65                 cross_v3_v3v3(no, vec1, vec2);
66                 if (dot_v3v3(no, no) == 0.0f) {
67                         no[0] = no[1] = 0.0f; no[2] = -1.0f;    
68                 }
69                 
70                 inv = dot_v3v3(no, up) < 0.0f;
71         }
72         
73         /*calculate normal*/
74         sub_v3_v3v3(vec1, v1, v2);
75         sub_v3_v3v3(vec2, v4, v3);
76         
77 #if 0
78         cross_v3_v3v3(no, vec2, vec1);
79         normalize_v3(no);
80         
81         if (dot_v3v3(no, no) < FLT_EPSILON*10) {
82                 copy_v3_v3(no, l->f->no);
83         }
84         
85         if (dot_v3v3(no, no) < FLT_EPSILON*10) {
86                 no[0] = 0.0; no[1] = 0.0; no[2] = 1.0f;
87         }
88         
89         /*compute offsets*/
90         l1 = len_v3(vec1)*fac; //(1.0-(cos(angle_v3v3(vec1, vec2))*0.5+0.5))
91         l2 = len_v3(vec2)*fac;
92
93         l2 = (l1 + l2)*0.5;
94         l1 = l2;
95         if (dot_v3v3(no, l->f->no) < 0.0) {
96                 negate_v3(no);
97         }       
98         
99         /*compute tangent and offset first edge*/
100         cross_v3_v3v3(tan, vec1, no);
101         normalize_v3(tan);
102
103         mul_v3_fl(tan, l1);
104         
105         add_v3_v3(v1, tan);
106         add_v3_v3(v2, tan);
107         
108         /*compute tangent and offset second edge*/
109         cross_v3_v3v3(tan, no, vec2);
110         normalize_v3(tan);
111         
112         mul_v3_fl(tan, l2);
113
114         add_v3_v3(v3, tan);
115         add_v3_v3(v4, tan);
116         
117         /*compute intersection*/
118         ret = isect_line_line_v3(v1, v2, v3, v4, p1, p2);
119         
120         if (ret==1) {
121                 copy_v3_v3(co, p1);
122         } else if (ret==2) {
123                 add_v3_v3v3(co, p1, p2);
124                 mul_v3_fl(co, 0.5);
125         } else { /*colinear case*/
126                 add_v3_v3v3(co, v2, v3);
127                 mul_v3_fl(co, 0.5);
128         }
129 #else
130         /*oddly, this simplistic method seems to work the best*/
131         add_v3_v3(vec1, vec2);
132         mul_v3_fl(vec1, fac * 0.5);
133
134         if (inv)
135                 negate_v3(vec1);
136         
137         add_v3_v3v3(co, vec1, l->v->co);
138 #endif
139 }
140
141 #define ETAG_SET(e, v, nv) (v) == (e)->v1 ? (etags[BM_GetIndex((e))].newv1 = (nv)) : (etags[BM_GetIndex((e))].newv2 = (nv))
142 #define ETAG_GET(e, v) ((v) == (e)->v1 ? (etags[BM_GetIndex((e))].newv1) : (etags[BM_GetIndex((e))].newv2))
143
144 void bmesh_bevel_exec(BMesh *bm, BMOperator *op)
145 {
146         BMOIter siter;
147         BMIter iter;
148         BMEdge *e;
149         BMVert *v;
150         BMFace **faces = NULL, *f;
151         LoopTag *tags=NULL, *tag;
152         EdgeTag *etags = NULL;
153         BMVert **verts = NULL;
154         BMEdge **edges = NULL;
155         BLI_array_declare(faces);
156         BLI_array_declare(tags);
157         BLI_array_declare(etags);
158         BLI_array_declare(verts);
159         BLI_array_declare(edges);
160         SmallHash hash;
161         float fac = BMO_Get_Float(op, "percent");
162         int i, li, has_elens, HasMDisps = CustomData_has_layer(&bm->ldata, CD_MDISPS);
163         
164         has_elens = CustomData_has_layer(&bm->edata, CD_PROP_FLT) && BMO_Get_Int(op, "uselengths");
165         if (has_elens) {
166                 li = BMO_Get_Int(op, "lengthlayer");
167         }
168         
169         BLI_smallhash_init(&hash);
170         
171         BMO_ITER(e, &siter, bm, op, "geom", BM_EDGE) {
172                 BMO_SetFlag(bm, e, BEVEL_FLAG|BEVEL_DEL);
173                 BMO_SetFlag(bm, e->v1, BEVEL_FLAG|BEVEL_DEL);
174                 BMO_SetFlag(bm, e->v2, BEVEL_FLAG|BEVEL_DEL);
175                 
176                 if (BM_Edge_FaceCount(e) < 2) {
177                         BMO_ClearFlag(bm, e, BEVEL_DEL);
178                         BMO_ClearFlag(bm, e->v1, BEVEL_DEL);
179                         BMO_ClearFlag(bm, e->v2, BEVEL_DEL);
180                 }
181 #if 0
182                 if (BM_Edge_FaceCount(e) == 0) {
183                         BMVert *verts[2] = {e->v1, e->v2};
184                         BMEdge *edges[2] = {e, BM_Make_Edge(bm, e->v1, e->v2, e, 0)};
185                         
186                         BMO_SetFlag(bm, edges[1], BEVEL_FLAG);
187                         BM_Make_Face(bm, verts, edges, 2, 0);
188                 }
189 #endif
190         }
191         
192         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
193                 BMO_SetFlag(bm, v, VERT_OLD);
194         }
195
196 #if 0
197         //a bit of cleaner code that, alas, doens't work.
198         /*build edge tags*/
199         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
200                 if (BMO_TestFlag(bm, e->v1, BEVEL_FLAG) || BMO_TestFlag(bm, e->v2, BEVEL_FLAG)) {
201                         BMIter liter;
202                         BMLoop *l;
203                         
204                         if (!BMO_TestFlag(bm, e, EDGE_OLD)) {
205                                 BM_SetIndex(e, BLI_array_count(etags));
206                                 BLI_array_growone(etags);
207                                 
208                                 BMO_SetFlag(bm, e, EDGE_OLD);
209                         }
210                         
211                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_EDGE, e) {
212                                 BMLoop *l2;
213                                 BMIter liter2;
214                                 
215                                 if (BMO_TestFlag(bm, l->f, BEVEL_FLAG))
216                                         continue;
217                         
218                                 BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_FACE, l->f) {
219                                         BM_SetIndex(l2, BLI_array_count(tags));
220                                         BLI_array_growone(tags);
221
222                                         if (!BMO_TestFlag(bm, l2->e, EDGE_OLD)) {
223                                                 BM_SetIndex(l2->e, BLI_array_count(etags));
224                                                 BLI_array_growone(etags);
225                                                 
226                                                 BMO_SetFlag(bm, l2->e, EDGE_OLD);
227                                         }
228                                 }
229
230                                 BMO_SetFlag(bm, l->f, BEVEL_FLAG);
231                                 BLI_array_append(faces, l->f);
232                         }
233                 } else {
234                         BM_SetIndex(e, -1);
235                 }
236         }
237 #endif
238         
239         /*create and assign looptag structures*/
240         BMO_ITER(e, &siter, bm, op, "geom", BM_EDGE) {
241                 BMLoop *l;
242                 BMIter liter;
243
244                 BMO_SetFlag(bm, e->v1, BEVEL_FLAG|BEVEL_DEL);
245                 BMO_SetFlag(bm, e->v2, BEVEL_FLAG|BEVEL_DEL);
246                 
247                 if (BM_Edge_FaceCount(e) < 2) {
248                         BMO_ClearFlag(bm, e, BEVEL_DEL);
249                         BMO_ClearFlag(bm, e->v1, BEVEL_DEL);
250                         BMO_ClearFlag(bm, e->v2, BEVEL_DEL);
251                 }
252                 
253                 if (!BLI_smallhash_haskey(&hash, (intptr_t)e)) {
254                         BLI_array_growone(etags);
255                         BM_SetIndex(e, BLI_array_count(etags)-1);
256                         BLI_smallhash_insert(&hash, (intptr_t)e, NULL);
257                         BMO_SetFlag(bm, e, EDGE_OLD);
258                 }
259                 
260                 /*find all faces surrounding e->v1 and, e->v2*/
261                 for (i=0; i<2; i++) {
262                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, i?e->v2:e->v1) {
263                                 BMLoop *l2;
264                                 BMIter liter2;
265                                 
266                                 /*see if we've already processed this loop's face*/
267                                 if (BLI_smallhash_haskey(&hash, (intptr_t)l->f))
268                                         continue;
269                                 
270                                 /*create tags for all loops in l->f*/
271                                 BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_FACE, l->f) {
272                                         BLI_array_growone(tags);
273                                         BM_SetIndex(l2, BLI_array_count(tags)-1);
274                                         
275                                         if (!BLI_smallhash_haskey(&hash, (intptr_t)l2->e)) {
276                                                 BLI_array_growone(etags);
277                                                 BM_SetIndex(l2->e, BLI_array_count(etags)-1);
278                                                 BLI_smallhash_insert(&hash, (intptr_t)l2->e, NULL);                                             
279                                                 BMO_SetFlag(bm, l2->e, EDGE_OLD);
280                                         }
281                                 }
282         
283                                 BLI_smallhash_insert(&hash, (intptr_t)l->f, NULL);
284                                 BMO_SetFlag(bm, l->f, BEVEL_FLAG);
285                                 BLI_array_append(faces, l->f);
286                         }
287                 }
288         }
289
290         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
291                 BMIter eiter;
292                 
293                 if (!BMO_TestFlag(bm, v, BEVEL_FLAG))
294                         continue;
295                 
296                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
297                         if (!BMO_TestFlag(bm, e, BEVEL_FLAG) && !ETAG_GET(e, v)) {
298                                 BMVert *v2;
299                                 float co[3];
300                                 
301                                 v2 = BM_OtherEdgeVert(e, v);
302                                 sub_v3_v3v3(co, v2->co, v->co);
303                                 if (has_elens) {
304                                         float elen = *(float*)CustomData_bmesh_get_n(&bm->edata, e->head.data, CD_PROP_FLT, li);
305
306                                         normalize_v3(co);
307                                         mul_v3_fl(co, elen);
308                                 }
309                                 
310                                 mul_v3_fl(co, fac);
311                                 add_v3_v3(co, v->co);
312                                 
313                                 v2 = BM_Make_Vert(bm, co, v);
314                                 ETAG_SET(e, v, v2);
315                         }
316                 }
317         }
318         
319         for (i=0; i<BLI_array_count(faces); i++) {
320                 BMLoop *l;
321                 BMIter liter;
322                 
323                 BMO_SetFlag(bm, faces[i], FACE_OLD);
324                 
325                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, faces[i]) {
326                         float co[3];
327
328                         if (BMO_TestFlag(bm, l->e, BEVEL_FLAG)) {
329                                 if (BMO_TestFlag(bm, l->prev->e, BEVEL_FLAG))
330                                 {
331                                         tag = tags + BM_GetIndex(l);
332                                         calc_corner_co(bm, l, co, fac);
333                                         tag->newv = BM_Make_Vert(bm, co, l->v);
334                                 } else {
335                                         tag = tags + BM_GetIndex(l);
336                                         tag->newv = ETAG_GET(l->prev->e, l->v);
337                                         
338                                         if (!tag->newv) {
339                                                 sub_v3_v3v3(co, l->prev->v->co, l->v->co);
340                                                 if (has_elens) {
341                                                         float elen = *(float*)CustomData_bmesh_get_n(&bm->edata, l->prev->e->head.data, CD_PROP_FLT, li);
342
343                                                         normalize_v3(co);
344                                                         mul_v3_fl(co, elen);
345                                                 }
346                                                                 
347                                                 mul_v3_fl(co, fac);
348                                                 add_v3_v3(co, l->v->co);
349                                         
350                                                 tag->newv = BM_Make_Vert(bm, co, l->v);
351                                                 
352                                                 ETAG_SET(l->prev->e, l->v, tag->newv);
353                                         }
354                                 }
355                         } else if (BMO_TestFlag(bm, l->v, BEVEL_FLAG)) {
356                                 tag = tags + BM_GetIndex(l);
357                                 tag->newv = ETAG_GET(l->e, l->v);                               
358                 
359                                 if (!tag->newv) {
360                                         sub_v3_v3v3(co, l->next->v->co, l->v->co);
361                                         if (has_elens) {
362                                                 float elen = *(float*)CustomData_bmesh_get_n(&bm->edata, l->e->head.data, CD_PROP_FLT, li);
363
364                                                 normalize_v3(co);
365                                                 mul_v3_fl(co, elen);
366                                         }
367                                         
368                                         mul_v3_fl(co, fac);
369                                         add_v3_v3(co, l->v->co);
370                         
371                                         tag = tags + BM_GetIndex(l);
372                                         tag->newv = BM_Make_Vert(bm, co, l->v);
373                                         
374                                         ETAG_SET(l->e, l->v, tag->newv);
375                                 }                                       
376                         } else {
377                                 tag = tags + BM_GetIndex(l);
378                                 tag->newv = l->v;
379                                 BMO_ClearFlag(bm, l->v, BEVEL_DEL);
380                         }
381                 }
382         }
383         
384         /*create new faces inset from original faces*/
385         for (i=0; i<BLI_array_count(faces); i++) {
386                 BMLoop *l;
387                 BMIter liter;
388                 BMFace *f;
389                 BMVert *lastv=NULL, *firstv=NULL;
390
391                 BMO_SetFlag(bm, faces[i], BEVEL_DEL);
392                 
393                 BLI_array_empty(verts);
394                 BLI_array_empty(edges);
395                 
396                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, faces[i]) {
397                         BMVert *v2;
398                         
399                         tag = tags + BM_GetIndex(l);
400                         BLI_array_append(verts, tag->newv);
401                         
402                         if (!firstv)
403                                 firstv = tag->newv;
404                         
405                         if (lastv) {
406                                 e = BM_Make_Edge(bm, lastv, tag->newv, l->e, 1);
407                                 BM_Copy_Attributes(bm, bm, l->prev->e, e);
408                                 BLI_array_append(edges, e);
409                         }
410                         lastv=tag->newv;
411                         
412                         v2 = ETAG_GET(l->e, l->next->v);
413                         
414                         tag = tags + BM_GetIndex(l->next);
415                         if (!BMO_TestFlag(bm, l->e, BEVEL_FLAG) && v2 && v2 != tag->newv) {
416                                 BLI_array_append(verts, v2);
417                                 
418                                 e = BM_Make_Edge(bm, lastv, v2, l->e, 1);
419                                 BM_Copy_Attributes(bm, bm, l->e, e);
420                                 
421                                 BLI_array_append(edges, e);
422                                 lastv = v2;
423                         }
424                 }
425                 
426                 e = BM_Make_Edge(bm, firstv, lastv, bm_firstfaceloop(faces[i])->e, 1);
427                 if (bm_firstfaceloop(faces[i])->prev->e != e) 
428                         BM_Copy_Attributes(bm, bm, bm_firstfaceloop(faces[i])->prev->e, e);
429                 BLI_array_append(edges, e);
430                 
431                 f = BM_Make_Ngon(bm, verts[0], verts[1], edges, BLI_array_count(edges), 0);
432                 if (!f) {
433                         printf("%s: could not make face!\n", __func__);
434                         continue;
435                 }
436                         
437                 BMO_SetFlag(bm, f, FACE_NEW);
438         }
439
440         for (i=0; i<BLI_array_count(faces); i++) {
441                 BMLoop *l;
442                 BMIter liter;
443                 int j;
444                 
445                 /*create quad spans between split edges*/
446                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, faces[i]) {
447                         BMVert *v1=NULL, *v2=NULL, *v3=NULL, *v4=NULL;
448                         
449                         if (!BMO_TestFlag(bm, l->e, BEVEL_FLAG))
450                                 continue;
451                         
452                         v1 = tags[BM_GetIndex(l)].newv;
453                         v2 = tags[BM_GetIndex(l->next)].newv;
454                         if (l->radial_next != l) {
455                                 v3 = tags[BM_GetIndex(l->radial_next)].newv;
456                                 if (l->radial_next->next->v == l->next->v) {
457                                         v4 = v3;
458                                         v3 = tags[BM_GetIndex(l->radial_next->next)].newv;
459                                 } else {
460                                         v4 = tags[BM_GetIndex(l->radial_next->next)].newv;
461                                 }
462                         } else {
463                                 /*the loop is on a boundary*/
464                                 v3 = l->next->v;
465                                 v4 = l->v;
466                                 
467                                 for (j=0; j<2; j++) {
468                                         BMIter eiter;
469                                         BMVert *v = j ? v4 : v3;
470
471                                         BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
472                                                 if (!BM_Vert_In_Edge(e, v3) || !BM_Vert_In_Edge(e, v4))
473                                                         continue;
474                                                 
475                                                 if (!BMO_TestFlag(bm, e, BEVEL_FLAG) && BMO_TestFlag(bm, e, EDGE_OLD)) {
476                                                         BMVert *vv;
477                                                         
478                                                         vv = ETAG_GET(e, v);
479                                                         if (!vv || BMO_TestFlag(bm, vv, BEVEL_FLAG))
480                                                                 continue;
481                                                         
482                                                         if (j)
483                                                                 v1 = vv;
484                                                         else
485                                                                 v2 = vv;
486                                                         break;
487                                                 }
488                                         }
489                                 }
490
491                                 BMO_ClearFlag(bm, v3, BEVEL_DEL);
492                                 BMO_ClearFlag(bm, v4, BEVEL_DEL);
493                         }
494                         
495                         if (v1 != v2 && v2 != v3 && v3 != v4) {
496                                 BMIter liter2;
497                                 BMLoop *l2, *l3;
498                                 BMEdge *e1, *e2;
499                                 float d1, d2, *d3;
500                                 
501                                 f = BM_Make_QuadTri(bm, v4, v3, v2, v1, l->f, 1);
502
503                                 e1 = BM_Edge_Exist(v4, v3);
504                                 e2 = BM_Edge_Exist(v2, v1);
505                                 BM_Copy_Attributes(bm, bm, l->e, e1);
506                                 BM_Copy_Attributes(bm, bm, l->e, e2);
507                                 
508                                 /*set edge lengths of cross edges as the average of the cross edges they're based on*/
509                                 if (has_elens) {
510 #if 0                           /* angle happens not to be used. why? - not sure it just isnt - campbell. leave this in incase we need to use it later */
511                                         float ang;
512 #endif
513                                         e1 = BM_Edge_Exist(v1, v4);
514                                         e2 = BM_Edge_Exist(v2, v3);
515                                         
516                                         if (l->radial_next->v == l->v) {
517                                                 l2 = l->radial_next->prev;
518                                                 l3 = l->radial_next->next;
519                                         } else {
520                                                 l2 = l->radial_next->next;
521                                                 l3 = l->radial_next->prev;
522                                         }
523                                         
524                                         d3 = CustomData_bmesh_get_n(&bm->edata, e1->head.data, CD_PROP_FLT, li);
525                                         d1 = *(float*)CustomData_bmesh_get_n(&bm->edata, l->prev->e->head.data, CD_PROP_FLT, li);
526                                         d2 = *(float*)CustomData_bmesh_get_n(&bm->edata, l2->e->head.data, CD_PROP_FLT, li);
527 #if 0
528                                         ang = angle_v3v3v3(l->prev->v->co, l->v->co, BM_OtherEdgeVert(l2->e, l->v)->co);
529 #endif
530                                         *d3 = (d1+d2)*0.5f;
531                                         
532                                         d3 = CustomData_bmesh_get_n(&bm->edata, e2->head.data, CD_PROP_FLT, li);
533                                         d1 = *(float*)CustomData_bmesh_get_n(&bm->edata, l->next->e->head.data, CD_PROP_FLT, li);
534                                         d2 = *(float*)CustomData_bmesh_get_n(&bm->edata, l3->e->head.data, CD_PROP_FLT, li);
535 #if 0
536                                         ang = angle_v3v3v3(BM_OtherEdgeVert(l->next->e, l->next->v)->co, l->next->v->co, BM_OtherEdgeVert(l3->e, l->next->v)->co);
537 #endif
538                                         *d3 = (d1+d2)*0.5f;
539                                 }
540
541                                 if (!f) {
542                                         fprintf(stderr, "%s: face index out of range! (bmesh internal error)\n", __func__);
543                                         continue;
544                                 }
545                                 
546                                 BMO_SetFlag(bm, f, FACE_NEW|FACE_SPAN);
547                                 
548                                 /*un-tag edges in f for deletion*/
549                                 BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_FACE, f) {
550                                         BMO_ClearFlag(bm, l2->e, BEVEL_DEL);
551                                 }
552                         } else {
553                                 f = NULL;
554                         }
555                 }       
556         }
557         
558         /*fill in holes at vertices*/
559         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
560                 BMIter eiter;
561                 BMVert *vv, *vstart=NULL, *lastv=NULL;
562                 SmallHash tmphash;
563                 int rad, insorig=0, err=0;
564                 
565                 BLI_smallhash_init(&tmphash);
566                 
567                 if (!BMO_TestFlag(bm, v, BEVEL_FLAG))
568                         continue;
569                 
570                 BLI_array_empty(verts);
571                 BLI_array_empty(edges);
572                 
573                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
574                         BMIter liter;
575                         BMVert *v1=NULL, *v2=NULL;
576                         BMLoop *l;
577                         
578                         if (BM_Edge_FaceCount(e) < 2)
579                                 insorig = 1;
580                         
581                         rad = 0;
582                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_EDGE, e) {
583                                 if (!BMO_TestFlag(bm, l->f, FACE_OLD))
584                                         continue;
585                                 
586                                 rad++;
587                                 
588                                 if (l->v == v)
589                                         tag = tags + BM_GetIndex(l);
590                                 else
591                                         tag = tags + BM_GetIndex(l->next);
592                                 
593                                 if (!v1)
594                                         v1 = tag->newv;
595                                 else if (!v2)
596                                         v2 = tag->newv;
597                         }
598                         
599                         if (rad < 2)
600                                 insorig = 1;
601                         
602                         if (!v1)
603                                 v1 = ETAG_GET(e, v);
604                         if (!v2 || v1 == v2)
605                                 v2 = ETAG_GET(e, v);
606                         
607                         if (v1) {
608                                 if (!BLI_smallhash_haskey(&tmphash, (intptr_t)v1)) {
609                                         BLI_array_append(verts, v1);
610                                         BLI_smallhash_insert(&tmphash, (intptr_t)v1, NULL);
611                                 }
612                                 
613                                 if (v2 && v1 != v2 && !BLI_smallhash_haskey(&tmphash, (intptr_t)v2)) {
614                                         BLI_array_append(verts, v2);
615                                         BLI_smallhash_insert(&tmphash, (intptr_t)v2, NULL);
616                                 }
617                         }
618                 }
619                 
620                 if (!BLI_array_count(verts))
621                         continue;
622                 
623                 if (insorig) {
624                         BLI_array_append(verts, v);
625                         BLI_smallhash_insert(&tmphash, (intptr_t)v, NULL);
626                 }
627                 
628                 /*find edges that exist between vertices in verts.  this is basically
629                   a topological walk of the edges connecting them.*/
630                 vstart = vstart ? vstart : verts[0];
631                 vv = vstart;
632                 do {
633                         BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, vv) {
634                                 BMVert *vv2 = BM_OtherEdgeVert(e, vv);
635                                 
636                                 if (vv2 != lastv && BLI_smallhash_haskey(&tmphash, (intptr_t)vv2)) {
637                                         /*if we've go over the same vert twice, break out of outer loop*/
638                                         if (BLI_smallhash_lookup(&tmphash, (intptr_t)vv2) != NULL) {
639                                                 e = NULL;
640                                                 err = 1;
641                                                 break;
642                                         }
643                                         
644                                         /*use self pointer as tag*/
645                                         BLI_smallhash_remove(&tmphash, (intptr_t)vv2);
646                                         BLI_smallhash_insert(&tmphash, (intptr_t)vv2, vv2);
647                                         
648                                         lastv = vv;
649                                         BLI_array_append(edges, e);
650                                         vv = vv2;
651                                         break;
652                                 }
653                         }
654                         if (e == NULL)
655                                 break;
656                 } while (vv != vstart);
657                 
658                 if (err)
659                         continue;
660                 
661                 /*there may not be a complete loop of edges, so start again and make
662                   final edge afterwards.  in this case, the previous loop worked to
663                   find one of the two edges at the extremes.*/
664                 if (vv != vstart) {
665                         /*undo previous tagging*/
666                         for (i=0; i<BLI_array_count(verts); i++) {
667                                 BLI_smallhash_remove(&tmphash, (intptr_t)verts[i]);
668                                 BLI_smallhash_insert(&tmphash, (intptr_t)verts[i], NULL);
669                         }
670
671                         vstart = vv;
672                         lastv = NULL;
673                         BLI_array_empty(edges);
674                         do {
675                                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, vv) {
676                                         BMVert *vv2 = BM_OtherEdgeVert(e, vv);
677                                         
678                                         if (vv2 != lastv && BLI_smallhash_haskey(&tmphash, (intptr_t)vv2)) {
679                                                 /*if we've go over the same vert twice, break out of outer loop*/
680                                                 if (BLI_smallhash_lookup(&tmphash, (intptr_t)vv2) != NULL) {
681                                                         e = NULL;
682                                                         err = 1;
683                                                         break;
684                                                 }
685                                                 
686                                                 /*use self pointer as tag*/
687                                                 BLI_smallhash_remove(&tmphash, (intptr_t)vv2);
688                                                 BLI_smallhash_insert(&tmphash, (intptr_t)vv2, vv2);
689                                                 
690                                                 lastv = vv;
691                                                 BLI_array_append(edges, e);
692                                                 vv = vv2;
693                                                 break;
694                                         }
695                                 }
696                                 if (e == NULL)
697                                         break;
698                         } while (vv != vstart);
699                         
700                         if (!err) {
701                                 e = BM_Make_Edge(bm, vv, vstart, NULL, 1);
702                                 BLI_array_append(edges, e);
703                         }
704                 }
705                 
706                 if (err)
707                         continue;
708                 
709                 if (BLI_array_count(edges) >= 3) {
710                         BMFace *f;
711                         
712                         if (BM_Face_Exists(bm, verts, BLI_array_count(verts), &f))
713                                 continue;
714                         
715                         f = BM_Make_Ngon(bm, lastv, vstart, edges, BLI_array_count(edges), 0);
716                         if (!f) {
717                                 fprintf(stderr, "%s: in bevel vert fill! (bmesh internal error)\n", __func__);
718                         } else {
719                                 BMO_SetFlag(bm, f, FACE_NEW|FACE_HOLE);
720                         }
721                 }
722                 BLI_smallhash_release(&tmphash);
723         }
724         
725         /*copy over customdata*/
726         for (i=0; i<BLI_array_count(faces); i++) {
727                 BMLoop *l;
728                 BMIter liter;
729                 BMFace *f = faces[i];
730                 
731                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
732                         BMLoop *l2;
733                         BMIter liter2;
734                         
735                         tag = tags + BM_GetIndex(l);
736                         if (!tag->newv)
737                                 continue;
738                         
739                         BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_VERT, tag->newv) {
740                                 if (!BMO_TestFlag(bm, l2->f, FACE_NEW) || (l2->v != tag->newv && l2->v != l->v))
741                                         continue;
742                                 
743                                 if (tag->newv != l->v || HasMDisps) {
744                                         BM_Copy_Attributes(bm, bm, l->f, l2->f);
745                                         BM_loop_interp_from_face(bm, l2, l->f, 1, 1);
746                                 } else {
747                                         BM_Copy_Attributes(bm, bm, l->f, l2->f);
748                                         BM_Copy_Attributes(bm, bm, l, l2);
749                                 }
750                                 
751                                 if (HasMDisps) {
752                                         BMLoop *l3;
753                                         BMIter liter3;
754                                         
755                                         BM_ITER(l3, &liter3, bm, BM_LOOPS_OF_FACE, l2->f) {
756                                                 BM_loop_interp_multires(bm, l3, l->f);
757                                         }
758                                 }
759                         }
760                 }
761         }
762         
763         /*handle vertices along boundary edges*/
764         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
765                 if (BMO_TestFlag(bm, v, VERT_OLD) && BMO_TestFlag(bm, v, BEVEL_FLAG) && !BMO_TestFlag(bm, v, BEVEL_DEL)) {
766                         BMLoop *l;
767                         BMLoop *lorig=NULL;
768                         BMIter liter;
769                         
770                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, v) {
771                                 // BMIter liter2;
772                                 // BMLoop *l2 = l->v == v ? l : l->next, *l3;
773                                 
774                                 if (BMO_TestFlag(bm, l->f, FACE_OLD)) {
775                                         lorig = l;
776                                         break;
777                                 }
778                         }
779                         
780                         if (!lorig)
781                                 continue;
782                         
783                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, v) {
784                                 BMLoop *l2 = l->v == v ? l : l->next;
785                                 
786                                 BM_Copy_Attributes(bm, bm, lorig->f, l2->f);
787                                 BM_Copy_Attributes(bm, bm, lorig, l2);
788                         }
789                 }
790         }
791 #if 0
792         /*clean up any remaining 2-edged faces*/
793         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
794                 if (f->len == 2) {
795                         BMFace *faces[2] = {f, bm_firstfaceloop(f)->radial_next->f};
796                         
797                         if (faces[0] == faces[1])
798                                 BM_Kill_Face(bm, f);
799                         else
800                                 BM_Join_Faces(bm, faces, 2);
801                 }
802         }
803 #endif
804         
805         BMO_CallOpf(bm, "del geom=%fv context=%i", BEVEL_DEL, DEL_VERTS);
806
807         /*clean up any edges that might not get properly deleted*/
808         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
809                 if (BMO_TestFlag(bm, e, EDGE_OLD) && !e->l)
810                         BMO_SetFlag(bm, e, BEVEL_DEL);
811         }
812
813         BMO_CallOpf(bm, "del geom=%fe context=%i", BEVEL_DEL, DEL_EDGES);
814         BMO_CallOpf(bm, "del geom=%ff context=%i", BEVEL_DEL, DEL_FACES);
815         
816         BLI_smallhash_release(&hash);
817         BLI_array_free(tags);
818         BLI_array_free(etags);
819         BLI_array_free(verts);
820         BLI_array_free(edges);
821         BLI_array_free(faces);
822         
823         BMO_Flag_To_Slot(bm, op, "face_spans", FACE_SPAN, BM_FACE);
824         BMO_Flag_To_Slot(bm, op, "face_holes", FACE_HOLE, BM_FACE);
825 }