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