skip assigning vars for inline bmesh flag funcs, just cast.
[blender.git] / source / blender / bmesh / operators / bevel.c
1 #include "MEM_guardedalloc.h"
2
3 #include "BLI_utildefines.h"
4 #include "BLI_ghash.h"
5 #include "BLI_memarena.h"
6 #include "BLI_blenlib.h"
7 #include "BLI_array.h"
8 #include "BLI_math.h"
9 #include "BLI_array.h"
10 #include "BLI_utildefines.h"
11 #include "BLI_smallhash.h"
12
13 #include "bmesh.h"
14 #include "bmesh_operators_private.h"
15
16 #define BEVEL_FLAG      1
17 #define BEVEL_DEL       2
18 #define FACE_NEW        4
19 #define EDGE_OLD        8
20 #define FACE_OLD        16
21 #define FACE_DONE       32
22 #define VERT_OLD        64
23 #define FACE_SPAN       128
24 #define FACE_HOLE       256
25
26 typedef struct LoopTag {
27         BMVert *newv;
28 } LoopTag;
29
30 typedef struct EdgeTag {
31         BMVert *newv1, *newv2;
32 } EdgeTag;
33
34 static void calc_corner_co(BMesh *bm, BMLoop *l, float *co, float fac)
35 {
36         float  no[3], /*tan[3]*,*/ vec1[3], vec2[3], v1[3], v2[3], v3[3], v4[3];
37         /*float p1[3], p2[3], w[3];
38         float l1, l2;*/
39         int /*ret,*/ inv=0;
40         
41         if (l->f->len > 2) {
42                 copy_v3_v3(v1, l->prev->v->co);
43                 copy_v3_v3(v2, l->v->co);
44                 copy_v3_v3(v3, l->v->co);
45                 copy_v3_v3(v4, l->next->v->co);
46         } else {
47                 BMIter iter;
48                 BMLoop *l2;
49                 float up[3] = {0.0f, 0.0f, 1.0f};
50                 
51                 copy_v3_v3(v1, l->prev->v->co);
52                 copy_v3_v3(v2, l->v->co);
53                 copy_v3_v3(v3, l->v->co);
54                 
55                 BM_ITER(l2, &iter, bm, BM_LOOPS_OF_VERT, l->v) {
56                         if (l2->f != l->f) {
57                                 copy_v3_v3(v4, BM_OtherEdgeVert(l2->e, l2->next->v)->co);
58                                 break;
59                         }
60                 }
61                 
62                 sub_v3_v3v3(vec1, v1, v2);
63                 sub_v3_v3v3(vec2, v4, v3);
64
65                 cross_v3_v3v3(no, vec1, vec2);
66                 if (dot_v3v3(no, no) == 0.0) {
67                         no[0] = no[1] = 0.0f; no[2] = -1.0f;    
68                 }
69                 
70                 inv = dot_v3v3(no, up) < 0.0;
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         mul_v3_fl(vec1, fac);
132         mul_v3_fl(vec2, fac);
133         add_v3_v3(vec1, vec2);
134         mul_v3_fl(vec1, 0.5);
135
136         if (inv)
137                 negate_v3(vec1);
138         
139         add_v3_v3v3(co, vec1, l->v->co);
140 #endif
141 }
142
143 #define ETAG_SET(e, v, nv) (v) == (e)->v1 ? (etags[BM_GetIndex((e))].newv1 = (nv)) : (etags[BM_GetIndex((e))].newv2 = (nv))
144 #define ETAG_GET(e, v) ((v) == (e)->v1 ? (etags[BM_GetIndex((e))].newv1) : (etags[BM_GetIndex((e))].newv2))
145
146 void bmesh_bevel_exec(BMesh *bm, BMOperator *op)
147 {
148         BMOIter siter;
149         BMIter iter;
150         BMEdge *e;
151         BMVert *v;
152         BMFace **faces = NULL, *f;
153         LoopTag *tags=NULL, *tag;
154         EdgeTag *etags = NULL, *etag;
155         BMVert **verts = NULL;
156         BMEdge **edges = NULL;
157         BLI_array_declare(faces);
158         BLI_array_declare(tags);
159         BLI_array_declare(etags);
160         BLI_array_declare(verts);
161         BLI_array_declare(edges);
162         SmallHash hash;
163         float fac = BMO_Get_Float(op, "percent");
164         int i, li, has_elens, HasMDisps = CustomData_has_layer(&bm->ldata, CD_MDISPS);
165         
166         has_elens = CustomData_has_layer(&bm->edata, CD_PROP_FLT) && BMO_Get_Int(op, "uselengths");
167         if (has_elens) {
168                 li = BMO_Get_Int(op, "lengthlayer");
169         }
170         
171         BLI_smallhash_init(&hash);
172         
173         BMO_ITER(e, &siter, bm, op, "geom", BM_EDGE) {
174                 BMO_SetFlag(bm, e, BEVEL_FLAG|BEVEL_DEL);
175                 BMO_SetFlag(bm, e->v1, BEVEL_FLAG|BEVEL_DEL);
176                 BMO_SetFlag(bm, e->v2, BEVEL_FLAG|BEVEL_DEL);
177                 
178                 if (BM_Edge_FaceCount(e) < 2) {
179                         BMO_ClearFlag(bm, e, BEVEL_DEL);
180                         BMO_ClearFlag(bm, e->v1, BEVEL_DEL);
181                         BMO_ClearFlag(bm, e->v2, BEVEL_DEL);
182                 }
183 #if 0
184                 if (BM_Edge_FaceCount(e) == 0) {
185                         BMVert *verts[2] = {e->v1, e->v2};
186                         BMEdge *edges[2] = {e, BM_Make_Edge(bm, e->v1, e->v2, e, 0)};
187                         
188                         BMO_SetFlag(bm, edges[1], BEVEL_FLAG);
189                         BM_Make_Face(bm, verts, edges, 2);
190                 }
191 #endif
192         }
193         
194         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
195                 BMO_SetFlag(bm, v, VERT_OLD);
196         }
197
198 #if 0
199         //a bit of cleaner code that, alas, doens't work.
200         /*build edge tags*/
201         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
202                 if (BMO_TestFlag(bm, e->v1, BEVEL_FLAG) || BMO_TestFlag(bm, e->v2, BEVEL_FLAG)) {
203                         BMIter liter;
204                         BMLoop *l;
205                         
206                         if (!BMO_TestFlag(bm, e, EDGE_OLD)) {
207                                 BM_SetIndex(e, BLI_array_count(etags));
208                                 BLI_array_growone(etags);
209                                 
210                                 BMO_SetFlag(bm, e, EDGE_OLD);
211                         }
212                         
213                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_EDGE, e) {
214                                 BMLoop *l2;
215                                 BMIter liter2;
216                                 
217                                 if (BMO_TestFlag(bm, l->f, BEVEL_FLAG))
218                                         continue;
219                         
220                                 BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_FACE, l->f) {
221                                         BM_SetIndex(l2, BLI_array_count(tags));
222                                         BLI_array_growone(tags);
223
224                                         if (!BMO_TestFlag(bm, l2->e, EDGE_OLD)) {
225                                                 BM_SetIndex(l2->e, BLI_array_count(etags));
226                                                 BLI_array_growone(etags);
227                                                 
228                                                 BMO_SetFlag(bm, l2->e, EDGE_OLD);
229                                         }
230                                 }
231
232                                 BMO_SetFlag(bm, l->f, BEVEL_FLAG);
233                                 BLI_array_append(faces, l->f);
234                         }
235                 } else {
236                         BM_SetIndex(e, -1);
237                 }
238         }
239 #endif
240         
241         /*create and assign looptag structures*/
242         BMO_ITER(e, &siter, bm, op, "geom", BM_EDGE) {
243                 BMLoop *l;
244                 BMIter liter;
245
246                 BMO_SetFlag(bm, e->v1, BEVEL_FLAG|BEVEL_DEL);
247                 BMO_SetFlag(bm, e->v2, BEVEL_FLAG|BEVEL_DEL);
248                 
249                 if (BM_Edge_FaceCount(e) < 2) {
250                         BMO_ClearFlag(bm, e, BEVEL_DEL);
251                         BMO_ClearFlag(bm, e->v1, BEVEL_DEL);
252                         BMO_ClearFlag(bm, e->v2, BEVEL_DEL);
253                 }
254                 
255                 if (!BLI_smallhash_haskey(&hash, (intptr_t)e)) {
256                         BLI_array_growone(etags);
257                         BM_SetIndex(e, BLI_array_count(etags)-1);
258                         BLI_smallhash_insert(&hash, (intptr_t)e, NULL);
259                         BMO_SetFlag(bm, e, EDGE_OLD);
260                 }
261                 
262                 /*find all faces surrounding e->v1 and, e->v2*/
263                 for (i=0; i<2; i++) {
264                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, i?e->v2:e->v1) {
265                                 BMLoop *l2;
266                                 BMIter liter2;
267                                 
268                                 /*see if we've already processed this loop's face*/
269                                 if (BLI_smallhash_haskey(&hash, (intptr_t)l->f))
270                                         continue;
271                                 
272                                 /*create tags for all loops in l->f*/
273                                 BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_FACE, l->f) {
274                                         BLI_array_growone(tags);
275                                         BM_SetIndex(l2, BLI_array_count(tags)-1);
276                                         
277                                         if (!BLI_smallhash_haskey(&hash, (intptr_t)l2->e)) {
278                                                 BLI_array_growone(etags);
279                                                 BM_SetIndex(l2->e, BLI_array_count(etags)-1);
280                                                 BLI_smallhash_insert(&hash, (intptr_t)l2->e, NULL);                                             
281                                                 BMO_SetFlag(bm, l2->e, EDGE_OLD);
282                                         }
283                                 }
284         
285                                 BLI_smallhash_insert(&hash, (intptr_t)l->f, NULL);
286                                 BMO_SetFlag(bm, l->f, BEVEL_FLAG);
287                                 BLI_array_append(faces, l->f);
288                         }
289                 }
290         }
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*/
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                         etag = etags + BM_GetIndex(l->e);
415                         v2 = l->next->v == l->e->v1 ? etag->newv1 : etag->newv2;
416                         
417                         tag = tags + BM_GetIndex(l->next);
418                         if (!BMO_TestFlag(bm, l->e, BEVEL_FLAG) && v2 && v2 != tag->newv) {
419                                 BLI_array_append(verts, v2);
420                                 
421                                 e = BM_Make_Edge(bm, lastv, v2, l->e, 1);
422                                 BM_Copy_Attributes(bm, bm, l->e, e);
423                                 
424                                 BLI_array_append(edges, e);
425                                 lastv = v2;
426                         }
427                 }
428                 
429                 e = BM_Make_Edge(bm, firstv, lastv, bm_firstfaceloop(faces[i])->e, 1);
430                 if (bm_firstfaceloop(faces[i])->prev->e != e) 
431                         BM_Copy_Attributes(bm, bm, bm_firstfaceloop(faces[i])->prev->e, e);
432                 BLI_array_append(edges, e);
433                 
434                 f = BM_Make_Ngon(bm, verts[0], verts[1], edges, BLI_array_count(verts), 0);
435                 if (!f) {
436                         printf("eck!!\n");
437                         continue;
438                 }
439                         
440                 BMO_SetFlag(bm, f, FACE_NEW);
441         }
442
443         for (i=0; i<BLI_array_count(faces); i++) {
444                 BMLoop *l;
445                 BMIter liter;
446                 BMVert *lastv=NULL, *firstv=NULL;
447                 int j;
448                 
449                 /*create quad spans between split edges*/
450                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, faces[i]) {
451                         BMVert *v1=NULL, *v2=NULL, *v3=NULL, *v4=NULL;
452                         
453                         if (!BMO_TestFlag(bm, l->e, BEVEL_FLAG))
454                                 continue;
455                         
456                         v1 = tags[BM_GetIndex(l)].newv;
457                         v2 = tags[BM_GetIndex(l->next)].newv;
458                         if (l->radial_next != l) {
459                                 v3 = tags[BM_GetIndex(l->radial_next)].newv;
460                                 if (l->radial_next->next->v == l->next->v) {
461                                         v4 = v3;
462                                         v3 = tags[BM_GetIndex(l->radial_next->next)].newv;
463                                 } else {
464                                         v4 = tags[BM_GetIndex(l->radial_next->next)].newv;
465                                 }
466                         } else {
467                                 v3 = l->next->v;
468                                 v4 = l->v;
469                                 
470                                 for (j=0; j<2; j++) {
471                                         BMIter eiter;
472                                         BMVert *v = j ? v4 : v3;
473
474                                         BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
475                                                 if (!BM_Vert_In_Edge(e, v3) || !BM_Vert_In_Edge(e, v4))
476                                                         continue;
477                                                 
478                                                 if (!BMO_TestFlag(bm, e, BEVEL_FLAG) && BMO_TestFlag(bm, e, EDGE_OLD)) {
479                                                         BMVert *vv;
480                                                         
481                                                         vv = ETAG_GET(e, v);
482                                                         if (!vv || BMO_TestFlag(bm, vv, BEVEL_FLAG))
483                                                                 continue;
484                                                         
485                                                         if (j)
486                                                                 v1 = vv;
487                                                         else
488                                                                 v2 = vv;
489                                                         break;
490                                                 }
491                                         }
492                                 }
493
494                                 BMO_ClearFlag(bm, v3, BEVEL_DEL);
495                                 BMO_ClearFlag(bm, v4, BEVEL_DEL);
496                         }
497                         
498                         if (v1 != v2 && v2 != v3 && v3 != v4) {
499                                 BMIter liter2;
500                                 BMLoop *l2, *l3;
501                                 BMEdge *e1, *e2, *e3, *e4;
502                                 float d1, d2, *d3;
503                                 
504                                 f = BM_Make_QuadTri(bm, v4, v3, v2, v1, l->f, 1);
505
506                                 e1 = BM_Edge_Exist(v4, v3);
507                                 e2 = BM_Edge_Exist(v2, v1);
508                                 BM_Copy_Attributes(bm, bm, l->e, e1);
509                                 BM_Copy_Attributes(bm, bm, l->e, e2);
510                                 
511                                 /*set edge lengths of cross edges as the average of the cross edges they're based on*/
512                                 if (has_elens) {
513                                         float ang;
514                                         
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                                         
530                                         ang = angle_v3v3v3(l->prev->v->co, l->v->co, BM_OtherEdgeVert(l2->e, l->v)->co);
531                                         *d3 = (d1+d2)*0.5;
532                                         
533                                         d3 = CustomData_bmesh_get_n(&bm->edata, e2->head.data, CD_PROP_FLT, li);
534                                         d1 = *(float*)CustomData_bmesh_get_n(&bm->edata, l->next->e->head.data, CD_PROP_FLT, li);
535                                         d2 = *(float*)CustomData_bmesh_get_n(&bm->edata, l3->e->head.data, CD_PROP_FLT, li);
536
537                                         ang = angle_v3v3v3(BM_OtherEdgeVert(l->next->e, l->next->v)->co, l->next->v->co, BM_OtherEdgeVert(l3->e, l->next->v)->co);
538                                         *d3 = (d1+d2)*0.5;
539                                 }
540
541                                 if (!f) {
542                                         printf("eek!\n");
543                                         continue;
544                                 }
545                                 
546                                 BMO_SetFlag(bm, f, FACE_NEW|FACE_SPAN);
547                                 
548                                 /*un-tag edges in f for deletion*/
549                                 BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_FACE, f) {
550                                         BMO_ClearFlag(bm, l2->e, BEVEL_DEL);
551                                 }
552                         } else {
553                                 f = NULL;
554                         }
555                 }       
556         }
557         
558         /*fill in holes at vertices*/
559         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
560                 BMIter eiter;
561                 BMVert *vv, *vstart=NULL, *lastv=NULL;
562                 SmallHash tmphash;
563                 int rad, insorig=0, err=0;
564                 
565                 BLI_smallhash_init(&tmphash);
566                 
567                 if (!BMO_TestFlag(bm, v, BEVEL_FLAG))
568                         continue;
569                 
570                 BLI_array_empty(verts);
571                 BLI_array_empty(edges);
572                 
573                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
574                         BMIter liter;
575                         BMVert *v1=NULL, *v2=NULL;
576                         BMLoop *l;
577                         
578                         if (BM_Edge_FaceCount(e) < 2)
579                                 insorig = 1;
580                         
581                         rad = 0;
582                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_EDGE, e) {
583                                 if (!BMO_TestFlag(bm, l->f, FACE_OLD))
584                                         continue;
585                                 
586                                 rad++;
587                                 
588                                 if (l->v == v)
589                                         tag = tags + BM_GetIndex(l);
590                                 else
591                                         tag = tags + BM_GetIndex(l->next);
592                                 
593                                 if (!v1)
594                                         v1 = tag->newv;
595                                 else if (!v2);
596                                         v2 = tag->newv;
597                         }
598                         
599                         if (rad < 2)
600                                 insorig = 1;
601                         
602                         if (!v1)
603                                 v1 = ETAG_GET(e, v);
604                         if (!v2 || v1 == v2)
605                                 v2 = ETAG_GET(e, v);
606                         
607                         if (v1) {
608                                 if (!BLI_smallhash_haskey(&tmphash, (intptr_t)v1)) {
609                                         BLI_array_append(verts, v1);
610                                         BLI_smallhash_insert(&tmphash, (intptr_t)v1, NULL);
611                                 }
612                                 
613                                 if (v2 && v1 != v2 && !BLI_smallhash_haskey(&tmphash, (intptr_t)v2)) {
614                                         BLI_array_append(verts, v2);
615                                         BLI_smallhash_insert(&tmphash, (intptr_t)v2, NULL);
616                                 }
617                         }
618                 }
619                 
620                 if (!BLI_array_count(verts))
621                         continue;
622                 
623                 if (insorig) {
624                         BLI_array_append(verts, v);
625                         BLI_smallhash_insert(&tmphash, (intptr_t)v, NULL);
626                 }
627                 
628                 /*find edges that exist between vertices in verts.  this is basically
629           a topological walk of the edges connecting them.*/
630                 vstart = vstart ? vstart : verts[0];
631                 vv = vstart;
632                 do {
633                         BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, vv) {
634                                 BMVert *vv2 = BM_OtherEdgeVert(e, vv);
635                                 
636                                 if (vv2 != lastv && BLI_smallhash_haskey(&tmphash, (intptr_t)vv2)) {
637                                         /*if we've go over the same vert twice, break out of outer loop*/
638                                         if (BLI_smallhash_lookup(&tmphash, (intptr_t)vv2) != NULL) {
639                                                 e = NULL;
640                                                 err = 1;
641                                                 break;
642                                         }
643                                         
644                                         /*use self pointer as tag*/
645                                         BLI_smallhash_remove(&tmphash, (intptr_t)vv2);
646                                         BLI_smallhash_insert(&tmphash, (intptr_t)vv2, vv2);
647                                         
648                                         lastv = vv;
649                                         BLI_array_append(edges, e);
650                                         vv = vv2;
651                                         break;
652                                 }
653                         }
654                         if (e == NULL)
655                                 break;
656                 } while (vv != vstart);
657                 
658                 if (err)
659                         continue;
660                 
661                 /*there may not be a complete loop of edges, so start again and make
662           final edge afterwards.  in this case, the previous loop worked to
663           find one of the two edges at the extremes.*/
664                 if (vv != vstart) {
665                         /*undo previous tagging*/
666                         for (i=0; i<BLI_array_count(verts); i++) {
667                                 BLI_smallhash_remove(&tmphash, (intptr_t)verts[i]);
668                                 BLI_smallhash_insert(&tmphash, (intptr_t)verts[i], NULL);
669                         }
670
671                         vstart = vv;
672                         lastv = NULL;
673                         BLI_array_empty(edges);
674                         do {
675                                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, vv) {
676                                         BMVert *vv2 = BM_OtherEdgeVert(e, vv);
677                                         
678                                         if (vv2 != lastv && BLI_smallhash_haskey(&tmphash, (intptr_t)vv2)) {
679                                                 /*if we've go over the same vert twice, break out of outer loop*/
680                                                 if (BLI_smallhash_lookup(&tmphash, (intptr_t)vv2) != NULL) {
681                                                         e = NULL;
682                                                         err = 1;
683                                                         break;
684                                                 }
685                                                 
686                                                 /*use self pointer as tag*/
687                                                 BLI_smallhash_remove(&tmphash, (intptr_t)vv2);
688                                                 BLI_smallhash_insert(&tmphash, (intptr_t)vv2, vv2);
689                                                 
690                                                 lastv = vv;
691                                                 BLI_array_append(edges, e);
692                                                 vv = vv2;
693                                                 break;
694                                         }
695                                 }
696                                 if (e == NULL)
697                                         break;
698                         } while (vv != vstart);
699                         
700                         if (!err) {
701                                 e = BM_Make_Edge(bm, vv, vstart, NULL, 1);
702                                 BLI_array_append(edges, e);
703                         }
704                 }
705                 
706                 if (err)
707                         continue;
708                 
709                 if (BLI_array_count(edges) >= 3) {
710                         BMFace *f;
711                         
712                         if (BM_Face_Exists(bm, verts, BLI_array_count(verts), &f))
713                                 continue;
714                         
715                         f = BM_Make_Ngon(bm, lastv, vstart, edges, BLI_array_count(edges), 0);
716                         if (!f) {
717                                 printf("eek! in bevel vert fill!\n");
718                         } else 
719                                 BMO_SetFlag(bm, f, FACE_NEW|FACE_HOLE);
720                 }
721                 BLI_smallhash_release(&tmphash);
722         }
723         
724         /*copy over customdata*/
725         for (i=0; i<BLI_array_count(faces); i++) {
726                 BMLoop *l;
727                 BMIter liter;
728                 BMFace *f = faces[i];
729                 
730                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
731                         BMLoop *l2;
732                         BMIter liter2;
733                         
734                         tag = tags + BM_GetIndex(l);
735                         if (!tag->newv)
736                                 continue;
737                         
738                         BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_VERT, tag->newv) {
739                                 if (!BMO_TestFlag(bm, l2->f, FACE_NEW) || (l2->v != tag->newv && l2->v != l->v))
740                                         continue;
741                                 
742                                 if (tag->newv != l->v || HasMDisps) {
743                                         BM_Copy_Attributes(bm, bm, l->f, l2->f);
744                                         BM_loop_interp_from_face(bm, l2, l->f, 1, 1);
745                                 } else {
746                                         BM_Copy_Attributes(bm, bm, l->f, l2->f);
747                                         BM_Copy_Attributes(bm, bm, l, l2);
748                                 }
749                                 
750                                 if (HasMDisps) {
751                                         BMLoop *l3;
752                                         BMIter liter3;
753                                         
754                                         BM_ITER(l3, &liter3, bm, BM_LOOPS_OF_FACE, l2->f) {
755                                                 BM_loop_interp_multires(bm, l3, l->f);
756                                         }
757                                 }
758                         }
759                 }
760         }
761         
762         /*handle vertices along boundary edges*/
763         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
764                 if (BMO_TestFlag(bm, v, VERT_OLD) && BMO_TestFlag(bm, v, BEVEL_FLAG) && !BMO_TestFlag(bm, v, BEVEL_DEL)) {
765                         BMLoop *l;
766                         BMLoop *lorig=NULL;
767                         BMIter liter;
768                         
769                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, v) {
770                                 // BMIter liter2;
771                                 // BMLoop *l2 = l->v == v ? l : l->next, *l3;
772                                 
773                                 if (BMO_TestFlag(bm, l->f, FACE_OLD)) {
774                                         lorig = l;
775                                         break;
776                                 }
777                         }
778                         
779                         if (!lorig)
780                                 continue;
781                         
782                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, v) {
783                                 BMLoop *l2 = l->v == v ? l : l->next;
784                                 
785                                 BM_Copy_Attributes(bm, bm, lorig->f, l2->f);
786                                 BM_Copy_Attributes(bm, bm, lorig, l2);
787                         }
788                 }
789         }
790 #if 0
791         /*clean up any remainin 2-edged faces*/
792         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
793                 if (f->len == 2) {
794                         BMFace *faces[2] = {f, bm_firstfaceloop(f)->radial_next->f};
795                         
796                         if (faces[0] == faces[1])
797                                 BM_Kill_Face(bm, f);
798                         else
799                                 BM_Join_Faces(bm, faces, 2);
800                 }
801         }
802 #endif
803         
804         BMO_CallOpf(bm, "del geom=%fv context=%i", BEVEL_DEL, DEL_VERTS);
805
806         /*clean up any edges that might not get properly deleted*/
807         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
808                 if (BMO_TestFlag(bm, e, EDGE_OLD) && !e->l)
809                         BMO_SetFlag(bm, e, BEVEL_DEL);
810         }
811
812         BMO_CallOpf(bm, "del geom=%fe context=%i", BEVEL_DEL, DEL_EDGES);
813         BMO_CallOpf(bm, "del geom=%ff context=%i", BEVEL_DEL, DEL_FACES);
814         
815         BLI_smallhash_release(&hash);
816         BLI_array_free(tags);
817         BLI_array_free(etags);
818         BLI_array_free(verts);
819         BLI_array_free(edges);
820         BLI_array_free(faces);
821         
822         BMO_Flag_To_Slot(bm, op, "face_spans", FACE_SPAN, BM_FACE);
823         BMO_Flag_To_Slot(bm, op, "face_holes", FACE_HOLE, BM_FACE);
824 }