604c6abaa58d7c661b3c8a8c20dfcb8376e46844
[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], /*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)); /* set_dirty! */
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)); /* set_dirty! */
220                                         BLI_array_growone(tags);
221
222                                         if (!BMO_TestFlag(bm, l2->e, EDGE_OLD)) {
223                                                 BM_SetIndex(l2->e, BLI_array_count(etags)); /* set_dirty! */
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); /* set_dirty! */
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); /* set_dirty! */
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); /* set_loop */
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); /* set_dirty! */
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->elem_index_dirty |= BM_EDGE;
291         
292         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
293                 BMIter eiter;
294                 
295                 if (!BMO_TestFlag(bm, v, BEVEL_FLAG))
296                         continue;
297                 
298                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
299                         if (!BMO_TestFlag(bm, e, BEVEL_FLAG) && !ETAG_GET(e, v)) {
300                                 BMVert *v2;
301                                 float co[3];
302                                 
303                                 v2 = BM_OtherEdgeVert(e, v);
304                                 sub_v3_v3v3(co, v2->co, v->co);
305                                 if (has_elens) {
306                                         float elen = *(float*)CustomData_bmesh_get_n(&bm->edata, e->head.data, CD_PROP_FLT, li);
307
308                                         normalize_v3(co);
309                                         mul_v3_fl(co, elen);
310                                 }
311                                 
312                                 mul_v3_fl(co, fac);
313                                 add_v3_v3(co, v->co);
314                                 
315                                 v2 = BM_Make_Vert(bm, co, v);
316                                 ETAG_SET(e, v, v2);
317                         }
318                 }
319         }
320         
321         for (i=0; i<BLI_array_count(faces); i++) {
322                 BMLoop *l;
323                 BMIter liter;
324                 
325                 BMO_SetFlag(bm, faces[i], FACE_OLD);
326                 
327                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, faces[i]) {
328                         float co[3];
329
330                         if (BMO_TestFlag(bm, l->e, BEVEL_FLAG)) {
331                                 if (BMO_TestFlag(bm, l->prev->e, BEVEL_FLAG))
332                                 {
333                                         tag = tags + BM_GetIndex(l);
334                                         calc_corner_co(bm, l, co, fac);
335                                         tag->newv = BM_Make_Vert(bm, co, l->v);
336                                 } else {
337                                         tag = tags + BM_GetIndex(l);
338                                         tag->newv = ETAG_GET(l->prev->e, l->v);
339                                         
340                                         if (!tag->newv) {
341                                                 sub_v3_v3v3(co, l->prev->v->co, l->v->co);
342                                                 if (has_elens) {
343                                                         float elen = *(float*)CustomData_bmesh_get_n(&bm->edata, l->prev->e->head.data, CD_PROP_FLT, li);
344
345                                                         normalize_v3(co);
346                                                         mul_v3_fl(co, elen);
347                                                 }
348                                                                 
349                                                 mul_v3_fl(co, fac);
350                                                 add_v3_v3(co, l->v->co);
351                                         
352                                                 tag->newv = BM_Make_Vert(bm, co, l->v);
353                                                 
354                                                 ETAG_SET(l->prev->e, l->v, tag->newv);
355                                         }
356                                 }
357                         } else if (BMO_TestFlag(bm, l->v, BEVEL_FLAG)) {
358                                 tag = tags + BM_GetIndex(l);
359                                 tag->newv = ETAG_GET(l->e, l->v);                               
360                 
361                                 if (!tag->newv) {
362                                         sub_v3_v3v3(co, l->next->v->co, l->v->co);
363                                         if (has_elens) {
364                                                 float elen = *(float*)CustomData_bmesh_get_n(&bm->edata, l->e->head.data, CD_PROP_FLT, li);
365
366                                                 normalize_v3(co);
367                                                 mul_v3_fl(co, elen);
368                                         }
369                                         
370                                         mul_v3_fl(co, fac);
371                                         add_v3_v3(co, l->v->co);
372                         
373                                         tag = tags + BM_GetIndex(l);
374                                         tag->newv = BM_Make_Vert(bm, co, l->v);
375                                         
376                                         ETAG_SET(l->e, l->v, tag->newv);
377                                 }                                       
378                         } else {
379                                 tag = tags + BM_GetIndex(l);
380                                 tag->newv = l->v;
381                                 BMO_ClearFlag(bm, l->v, BEVEL_DEL);
382                         }
383                 }
384         }
385         
386         /*create new faces inset from original faces*/
387         for (i=0; i<BLI_array_count(faces); i++) {
388                 BMLoop *l;
389                 BMIter liter;
390                 BMFace *f;
391                 BMVert *lastv=NULL, *firstv=NULL;
392
393                 BMO_SetFlag(bm, faces[i], BEVEL_DEL);
394                 
395                 BLI_array_empty(verts);
396                 BLI_array_empty(edges);
397                 
398                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, faces[i]) {
399                         BMVert *v2;
400                         
401                         tag = tags + BM_GetIndex(l);
402                         BLI_array_append(verts, tag->newv);
403                         
404                         if (!firstv)
405                                 firstv = tag->newv;
406                         
407                         if (lastv) {
408                                 e = BM_Make_Edge(bm, lastv, tag->newv, l->e, 1);
409                                 BM_Copy_Attributes(bm, bm, l->prev->e, e);
410                                 BLI_array_append(edges, e);
411                         }
412                         lastv=tag->newv;
413                         
414                         v2 = ETAG_GET(l->e, l->next->v);
415                         
416                         tag = tags + BM_GetIndex(l->next);
417                         if (!BMO_TestFlag(bm, l->e, BEVEL_FLAG) && v2 && v2 != tag->newv) {
418                                 BLI_array_append(verts, v2);
419                                 
420                                 e = BM_Make_Edge(bm, lastv, v2, l->e, 1);
421                                 BM_Copy_Attributes(bm, bm, l->e, e);
422                                 
423                                 BLI_array_append(edges, e);
424                                 lastv = v2;
425                         }
426                 }
427                 
428                 e = BM_Make_Edge(bm, firstv, lastv, bm_firstfaceloop(faces[i])->e, 1);
429                 if (bm_firstfaceloop(faces[i])->prev->e != e) 
430                         BM_Copy_Attributes(bm, bm, bm_firstfaceloop(faces[i])->prev->e, e);
431                 BLI_array_append(edges, e);
432                 
433                 f = BM_Make_Ngon(bm, verts[0], verts[1], edges, BLI_array_count(edges), 0);
434                 if (!f) {
435                         printf("%s: could not make face!\n", __func__);
436                         continue;
437                 }
438                         
439                 BMO_SetFlag(bm, f, FACE_NEW);
440         }
441
442         for (i=0; i<BLI_array_count(faces); i++) {
443                 BMLoop *l;
444                 BMIter liter;
445                 int j;
446                 
447                 /*create quad spans between split edges*/
448                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, faces[i]) {
449                         BMVert *v1=NULL, *v2=NULL, *v3=NULL, *v4=NULL;
450                         
451                         if (!BMO_TestFlag(bm, l->e, BEVEL_FLAG))
452                                 continue;
453                         
454                         v1 = tags[BM_GetIndex(l)].newv;
455                         v2 = tags[BM_GetIndex(l->next)].newv;
456                         if (l->radial_next != l) {
457                                 v3 = tags[BM_GetIndex(l->radial_next)].newv;
458                                 if (l->radial_next->next->v == l->next->v) {
459                                         v4 = v3;
460                                         v3 = tags[BM_GetIndex(l->radial_next->next)].newv;
461                                 } else {
462                                         v4 = tags[BM_GetIndex(l->radial_next->next)].newv;
463                                 }
464                         } else {
465                                 /*the loop is on a boundary*/
466                                 v3 = l->next->v;
467                                 v4 = l->v;
468                                 
469                                 for (j=0; j<2; j++) {
470                                         BMIter eiter;
471                                         BMVert *v = j ? v4 : v3;
472
473                                         BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
474                                                 if (!BM_Vert_In_Edge(e, v3) || !BM_Vert_In_Edge(e, v4))
475                                                         continue;
476                                                 
477                                                 if (!BMO_TestFlag(bm, e, BEVEL_FLAG) && BMO_TestFlag(bm, e, EDGE_OLD)) {
478                                                         BMVert *vv;
479                                                         
480                                                         vv = ETAG_GET(e, v);
481                                                         if (!vv || BMO_TestFlag(bm, vv, BEVEL_FLAG))
482                                                                 continue;
483                                                         
484                                                         if (j)
485                                                                 v1 = vv;
486                                                         else
487                                                                 v2 = vv;
488                                                         break;
489                                                 }
490                                         }
491                                 }
492
493                                 BMO_ClearFlag(bm, v3, BEVEL_DEL);
494                                 BMO_ClearFlag(bm, v4, BEVEL_DEL);
495                         }
496                         
497                         if (v1 != v2 && v2 != v3 && v3 != v4) {
498                                 BMIter liter2;
499                                 BMLoop *l2, *l3;
500                                 BMEdge *e1, *e2;
501                                 float d1, d2, *d3;
502                                 
503                                 f = BM_Make_QuadTri(bm, v4, v3, v2, v1, l->f, 1);
504
505                                 e1 = BM_Edge_Exist(v4, v3);
506                                 e2 = BM_Edge_Exist(v2, v1);
507                                 BM_Copy_Attributes(bm, bm, l->e, e1);
508                                 BM_Copy_Attributes(bm, bm, l->e, e2);
509                                 
510                                 /*set edge lengths of cross edges as the average of the cross edges they're based on*/
511                                 if (has_elens) {
512 #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 */
513                                         float ang;
514 #endif
515                                         e1 = BM_Edge_Exist(v1, v4);
516                                         e2 = BM_Edge_Exist(v2, v3);
517                                         
518                                         if (l->radial_next->v == l->v) {
519                                                 l2 = l->radial_next->prev;
520                                                 l3 = l->radial_next->next;
521                                         } else {
522                                                 l2 = l->radial_next->next;
523                                                 l3 = l->radial_next->prev;
524                                         }
525                                         
526                                         d3 = CustomData_bmesh_get_n(&bm->edata, e1->head.data, CD_PROP_FLT, li);
527                                         d1 = *(float*)CustomData_bmesh_get_n(&bm->edata, l->prev->e->head.data, CD_PROP_FLT, li);
528                                         d2 = *(float*)CustomData_bmesh_get_n(&bm->edata, l2->e->head.data, CD_PROP_FLT, li);
529 #if 0
530                                         ang = angle_v3v3v3(l->prev->v->co, l->v->co, BM_OtherEdgeVert(l2->e, l->v)->co);
531 #endif
532                                         *d3 = (d1+d2)*0.5f;
533                                         
534                                         d3 = CustomData_bmesh_get_n(&bm->edata, e2->head.data, CD_PROP_FLT, li);
535                                         d1 = *(float*)CustomData_bmesh_get_n(&bm->edata, l->next->e->head.data, CD_PROP_FLT, li);
536                                         d2 = *(float*)CustomData_bmesh_get_n(&bm->edata, l3->e->head.data, CD_PROP_FLT, li);
537 #if 0
538                                         ang = angle_v3v3v3(BM_OtherEdgeVert(l->next->e, l->next->v)->co, l->next->v->co, BM_OtherEdgeVert(l3->e, l->next->v)->co);
539 #endif
540                                         *d3 = (d1+d2)*0.5f;
541                                 }
542
543                                 if (!f) {
544                                         fprintf(stderr, "%s: face index out of range! (bmesh internal error)\n", __func__);
545                                         continue;
546                                 }
547                                 
548                                 BMO_SetFlag(bm, f, FACE_NEW|FACE_SPAN);
549                                 
550                                 /*un-tag edges in f for deletion*/
551                                 BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_FACE, f) {
552                                         BMO_ClearFlag(bm, l2->e, BEVEL_DEL);
553                                 }
554                         } else {
555                                 f = NULL;
556                         }
557                 }       
558         }
559         
560         /*fill in holes at vertices*/
561         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
562                 BMIter eiter;
563                 BMVert *vv, *vstart=NULL, *lastv=NULL;
564                 SmallHash tmphash;
565                 int rad, insorig=0, err=0;
566
567                 BLI_smallhash_init(&tmphash);
568                                 
569                 if (!BMO_TestFlag(bm, v, BEVEL_FLAG))
570                         continue;
571                 
572                 BLI_array_empty(verts);
573                 BLI_array_empty(edges);
574                 
575                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
576                         BMIter liter;
577                         BMVert *v1=NULL, *v2=NULL;
578                         BMLoop *l;
579                         
580                         if (BM_Edge_FaceCount(e) < 2)
581                                 insorig = 1;
582                         
583                         if (BM_GetIndex(e) == -1)
584                                 continue;
585                         
586                         rad = 0;
587                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_EDGE, e) {
588                                 if (!BMO_TestFlag(bm, l->f, FACE_OLD))
589                                         continue;
590                                 
591                                 rad++;
592                                 
593                                 if (l->v == v)
594                                         tag = tags + BM_GetIndex(l);
595                                 else
596                                         tag = tags + BM_GetIndex(l->next);
597                                 
598                                 if (!v1)
599                                         v1 = tag->newv;
600                                 else if (!v2)
601                                         v2 = tag->newv;
602                         }
603                         
604                         if (rad < 2)
605                                 insorig = 1;
606                         
607                         if (!v1)
608                                 v1 = ETAG_GET(e, v);
609                         if (!v2 || v1 == v2)
610                                 v2 = ETAG_GET(e, v);
611                         
612                         if (v1) {
613                                 if (!BLI_smallhash_haskey(&tmphash, (intptr_t)v1)) {
614                                         BLI_array_append(verts, v1);
615                                         BLI_smallhash_insert(&tmphash, (intptr_t)v1, NULL);
616                                 }
617                                 
618                                 if (v2 && v1 != v2 && !BLI_smallhash_haskey(&tmphash, (intptr_t)v2)) {
619                                         BLI_array_append(verts, v2);
620                                         BLI_smallhash_insert(&tmphash, (intptr_t)v2, NULL);
621                                 }
622                         }
623                 }
624                 
625                 if (!BLI_array_count(verts))
626                         continue;
627                 
628                 if (insorig) {
629                         BLI_array_append(verts, v);
630                         BLI_smallhash_insert(&tmphash, (intptr_t)v, NULL);
631                 }
632                 
633                 /*find edges that exist between vertices in verts.  this is basically
634                   a topological walk of the edges connecting them.*/
635                 vstart = vstart ? vstart : verts[0];
636                 vv = vstart;
637                 do {
638                         BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, vv) {
639                                 BMVert *vv2 = BM_OtherEdgeVert(e, vv);
640                                 
641                                 if (vv2 != lastv && BLI_smallhash_haskey(&tmphash, (intptr_t)vv2)) {
642                                         /*if we've go over the same vert twice, break out of outer loop*/
643                                         if (BLI_smallhash_lookup(&tmphash, (intptr_t)vv2) != NULL) {
644                                                 e = NULL;
645                                                 err = 1;
646                                                 break;
647                                         }
648                                         
649                                         /*use self pointer as tag*/
650                                         BLI_smallhash_remove(&tmphash, (intptr_t)vv2);
651                                         BLI_smallhash_insert(&tmphash, (intptr_t)vv2, vv2);
652                                         
653                                         lastv = vv;
654                                         BLI_array_append(edges, e);
655                                         vv = vv2;
656                                         break;
657                                 }
658                         }
659                         if (e == NULL)
660                                 break;
661                 } while (vv != vstart);
662                 
663                 if (err)
664                         continue;
665                 
666                 /*there may not be a complete loop of edges, so start again and make
667                   final edge afterwards.  in this case, the previous loop worked to
668                   find one of the two edges at the extremes.*/
669                 if (vv != vstart) {
670                         /*undo previous tagging*/
671                         for (i=0; i<BLI_array_count(verts); i++) {
672                                 BLI_smallhash_remove(&tmphash, (intptr_t)verts[i]);
673                                 BLI_smallhash_insert(&tmphash, (intptr_t)verts[i], NULL);
674                         }
675
676                         vstart = vv;
677                         lastv = NULL;
678                         BLI_array_empty(edges);
679                         do {
680                                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, vv) {
681                                         BMVert *vv2 = BM_OtherEdgeVert(e, vv);
682                                         
683                                         if (vv2 != lastv && BLI_smallhash_haskey(&tmphash, (intptr_t)vv2)) {
684                                                 /*if we've go over the same vert twice, break out of outer loop*/
685                                                 if (BLI_smallhash_lookup(&tmphash, (intptr_t)vv2) != NULL) {
686                                                         e = NULL;
687                                                         err = 1;
688                                                         break;
689                                                 }
690                                                 
691                                                 /*use self pointer as tag*/
692                                                 BLI_smallhash_remove(&tmphash, (intptr_t)vv2);
693                                                 BLI_smallhash_insert(&tmphash, (intptr_t)vv2, vv2);
694                                                 
695                                                 lastv = vv;
696                                                 BLI_array_append(edges, e);
697                                                 vv = vv2;
698                                                 break;
699                                         }
700                                 }
701                                 if (e == NULL)
702                                         break;
703                         } while (vv != vstart);
704                         
705                         if (!err) {
706                                 e = BM_Make_Edge(bm, vv, vstart, NULL, 1);
707                                 BLI_array_append(edges, e);
708                         }
709                 }
710                 
711                 if (err)
712                         continue;
713                 
714                 if (BLI_array_count(edges) >= 3) {
715                         BMFace *f;
716                         
717                         if (BM_Face_Exists(bm, verts, BLI_array_count(verts), &f))
718                                 continue;
719                         
720                         f = BM_Make_Ngon(bm, lastv, vstart, edges, BLI_array_count(edges), 0);
721                         if (!f) {
722                                 fprintf(stderr, "%s: in bevel vert fill! (bmesh internal error)\n", __func__);
723                         } else {
724                                 BMO_SetFlag(bm, f, FACE_NEW|FACE_HOLE);
725                         }
726                 }
727                 BLI_smallhash_release(&tmphash);
728         }
729         
730         /*copy over customdata*/
731         for (i=0; i<BLI_array_count(faces); i++) {
732                 BMLoop *l;
733                 BMIter liter;
734                 BMFace *f = faces[i];
735                 
736                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
737                         BMLoop *l2;
738                         BMIter liter2;
739                         
740                         tag = tags + BM_GetIndex(l);
741                         if (!tag->newv)
742                                 continue;
743                         
744                         BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_VERT, tag->newv) {
745                                 if (!BMO_TestFlag(bm, l2->f, FACE_NEW) || (l2->v != tag->newv && l2->v != l->v))
746                                         continue;
747                                 
748                                 if (tag->newv != l->v || HasMDisps) {
749                                         BM_Copy_Attributes(bm, bm, l->f, l2->f);
750                                         BM_loop_interp_from_face(bm, l2, l->f, 1, 1);
751                                 } else {
752                                         BM_Copy_Attributes(bm, bm, l->f, l2->f);
753                                         BM_Copy_Attributes(bm, bm, l, l2);
754                                 }
755                                 
756                                 if (HasMDisps) {
757                                         BMLoop *l3;
758                                         BMIter liter3;
759                                         
760                                         BM_ITER(l3, &liter3, bm, BM_LOOPS_OF_FACE, l2->f) {
761                                                 BM_loop_interp_multires(bm, l3, l->f);
762                                         }
763                                 }
764                         }
765                 }
766         }
767         
768         /*handle vertices along boundary edges*/
769         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
770                 if (BMO_TestFlag(bm, v, VERT_OLD) && BMO_TestFlag(bm, v, BEVEL_FLAG) && !BMO_TestFlag(bm, v, BEVEL_DEL)) {
771                         BMLoop *l;
772                         BMLoop *lorig=NULL;
773                         BMIter liter;
774                         
775                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, v) {
776                                 // BMIter liter2;
777                                 // BMLoop *l2 = l->v == v ? l : l->next, *l3;
778                                 
779                                 if (BMO_TestFlag(bm, l->f, FACE_OLD)) {
780                                         lorig = l;
781                                         break;
782                                 }
783                         }
784                         
785                         if (!lorig)
786                                 continue;
787                         
788                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, v) {
789                                 BMLoop *l2 = l->v == v ? l : l->next;
790                                 
791                                 BM_Copy_Attributes(bm, bm, lorig->f, l2->f);
792                                 BM_Copy_Attributes(bm, bm, lorig, l2);
793                         }
794                 }
795         }
796 #if 0
797         /*clean up any remaining 2-edged faces*/
798         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
799                 if (f->len == 2) {
800                         BMFace *faces[2] = {f, bm_firstfaceloop(f)->radial_next->f};
801                         
802                         if (faces[0] == faces[1])
803                                 BM_Kill_Face(bm, f);
804                         else
805                                 BM_Join_Faces(bm, faces, 2);
806                 }
807         }
808 #endif
809         
810         BMO_CallOpf(bm, "del geom=%fv context=%i", BEVEL_DEL, DEL_VERTS);
811
812         /*clean up any edges that might not get properly deleted*/
813         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
814                 if (BMO_TestFlag(bm, e, EDGE_OLD) && !e->l)
815                         BMO_SetFlag(bm, e, BEVEL_DEL);
816         }
817
818         BMO_CallOpf(bm, "del geom=%fe context=%i", BEVEL_DEL, DEL_EDGES);
819         BMO_CallOpf(bm, "del geom=%ff context=%i", BEVEL_DEL, DEL_FACES);
820         
821         BLI_smallhash_release(&hash);
822         BLI_array_free(tags);
823         BLI_array_free(etags);
824         BLI_array_free(verts);
825         BLI_array_free(edges);
826         BLI_array_free(faces);
827         
828         BMO_Flag_To_Slot(bm, op, "face_spans", FACE_SPAN, BM_FACE);
829         BMO_Flag_To_Slot(bm, op, "face_holes", FACE_HOLE, BM_FACE);
830 }