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