=bmesh=
[blender.git] / source / blender / bmesh / operators / bevel.c
1 #include "MEM_guardedalloc.h"
2
3 #include "BKE_utildefines.h"
4
5 #include "BLI_ghash.h"
6 #include "BLI_memarena.h"
7 #include "BLI_blenlib.h"
8 #include "BLI_array.h"
9 #include "BLI_math.h"
10 #include "BLI_array.h"
11 #include "BLI_utildefines.h"
12 #include "BLI_smallhash.h"
13
14 #include "bmesh.h"
15 #include "bmesh_operators_private.h"
16
17 #define BEVEL_FLAG      1
18 #define BEVEL_DEL       2
19 #define FACE_NEW        4
20 #define EDGE_OLD        8
21 #define FACE_OLD        16
22 #define FACE_DONE       32
23 #define VERT_OLD        64
24 #define FACE_SPAN       128
25 #define FACE_HOLE       256
26
27 typedef struct LoopTag {
28         BMVert *newv;
29 } LoopTag;
30
31 typedef struct EdgeTag {
32         BMVert *newv1, *newv2;
33 } EdgeTag;
34
35
36 /* "Projects" a vector perpendicular to vec2 against vec1, such that
37  * the projected vec1 + vec2 has a min distance of 1 from the "edge" defined by vec2.
38  * note: the direction, is_forward, is used in conjunction with up_vec to determine
39  * whether this is a convex or concave corner. If it is a concave corner, it will
40  * be projected "backwards." If vec1 is before vec2, is_forward should be 0 (we are projecting backwards).
41  * vec1 is the vector to project onto (expected to be normalized)
42  * vec2 is the direction of projection (pointing away from vec1)
43  * up_vec is used for orientation (expected to be normalized)
44  * returns the length of the projected vector that lies along vec1 */
45 static float BM_bevel_project_vec(float *vec1, float *vec2, float *up_vec, int is_forward) {
46         float factor, vec3[3], tmp[3],c1,c2;
47
48         cross_v3_v3v3(tmp,vec1,vec2);
49         normalize_v3(tmp);
50         factor = dot_v3v3(up_vec,tmp);
51         if ((factor > 0 && is_forward) || (factor < 0 && !is_forward)) {
52                 cross_v3_v3v3(vec3,vec2,tmp); /* hmm, maybe up_vec should be used instead of tmp */
53         }
54         else {
55                 cross_v3_v3v3(vec3,tmp,vec2); /* hmm, maybe up_vec should be used instead of tmp */
56         }
57         normalize_v3(vec3);
58         c1 = dot_v3v3(vec3,vec1);
59         c2 = dot_v3v3(vec1,vec1);
60         if (fabs(c1) < 0.000001f || fabs(c2) < 0.000001f) {
61                 factor = 0.0f;
62         }
63         else {
64                 factor = c2/c1;
65         }
66
67         return factor;
68 }
69
70 void calc_corner_co(BMesh *bm, BMLoop *l, float *co, float fac)
71 {
72         float no[3], tan[3], vec1[3], vec2[3], v1[3], v2[3], v3[3], v4[3];
73         float p1[3], p2[3], w[3];
74         float l1, l2;
75         int ret;
76
77         copy_v3_v3(v1, l->prev->v->co);
78         copy_v3_v3(v2, l->v->co);
79         copy_v3_v3(v3, l->v->co);
80         copy_v3_v3(v4, l->next->v->co);
81         
82         /*calculate normal*/
83         sub_v3_v3v3(vec1, v1, v2);
84         sub_v3_v3v3(vec2, v4, v3);
85 #if 0
86         cross_v3_v3v3(no, vec2, vec1);
87         normalize_v3(no);
88         
89         if (dot_v3v3(no, no) < DBL_EPSILON*10) {
90                 copy_v3_v3(no, l->f->no);
91         }
92         
93         /*compute offsets*/
94         l1 = len_v3(vec1)*fac;
95         l2 = len_v3(vec2)*fac;
96         if (dot_v3v3(no, l->f->no) < 0.0) {
97                 l1 = -l1;
98                 l2 = -l2;
99         }       
100         
101         /*compute tangent and offset first edge*/
102         cross_v3_v3v3(tan, vec1, no);
103         normalize_v3(tan);
104
105         mul_v3_fl(tan, l1);
106         
107         add_v3_v3(v1, tan);
108         add_v3_v3(v2, tan);
109         
110         /*compute tangent and offset second edge*/
111         cross_v3_v3v3(tan, no, vec2);
112         normalize_v3(tan);
113         
114         mul_v3_fl(tan, l2);
115
116         add_v3_v3(v3, tan);
117         add_v3_v3(v4, tan);
118         
119         /*compute intersection*/
120         ret = isect_line_line_v3(v1, v2, v3, v4, p1, p2);
121         if (ret==1) {
122                 copy_v3_v3(co, p1);
123         } else if (ret==2) {
124                 add_v3_v3v3(co, p1, p2);
125                 mul_v3_fl(co, 0.5);
126         } else { /*colinear case*/
127                 add_v3_v3v3(co, v2, v3);
128                 mul_v3_fl(co, 0.5);
129         }
130 #endif
131         /*oddly, this simplistic method seems to work the best*/
132         mul_v3_fl(vec1, fac);
133         mul_v3_fl(vec2, fac);
134         add_v3_v3(vec1, vec2);
135         mul_v3_fl(vec1, 0.5);
136         
137         add_v3_v3v3(co, vec1, l->v->co);
138 }
139
140 #define ETAG_SET(e, v, nv) (v) == (e)->v1 ? (etags[BMINDEX_GET((e))].newv1 = (nv)) : (etags[BMINDEX_GET((e))].newv2 = (nv))
141 #define ETAG_GET(e, v) ((v) == (e)->v1 ? (etags[BMINDEX_GET((e))].newv1) : (etags[BMINDEX_GET((e))].newv2))
142
143 void bmesh_bevel_exec(BMesh *bm, BMOperator *op)
144 {
145         BMOIter siter;
146         BMIter iter;
147         BMEdge *e;
148         BMVert *v;
149         BMFace **faces = NULL;
150         LoopTag *tags=NULL, *tag;
151         EdgeTag *etags = NULL, *etag;
152         BMVert **verts = NULL;
153         BMEdge **edges = NULL;
154         BLI_array_declare(faces);
155         BLI_array_declare(tags);
156         BLI_array_declare(etags);
157         BLI_array_declare(verts);
158         BLI_array_declare(edges);
159         SmallHash hash;
160         float fac = BMO_Get_Float(op, "percent");
161         int i;
162         
163         BLI_smallhash_init(&hash);
164         
165         BMO_ITER(e, &siter, bm, op, "geom", BM_EDGE) {
166                 BMO_SetFlag(bm, e, BEVEL_FLAG|BEVEL_DEL);
167                 BMO_SetFlag(bm, e->v1, BEVEL_FLAG|BEVEL_DEL);
168                 BMO_SetFlag(bm, e->v2, BEVEL_FLAG|BEVEL_DEL);
169                 
170                 if (BM_Edge_FaceCount(e) < 2) {
171                         BMO_ClearFlag(bm, e, BEVEL_DEL);
172                         BMO_ClearFlag(bm, e->v1, BEVEL_DEL);
173                         BMO_ClearFlag(bm, e->v2, BEVEL_DEL);
174                 }
175         }
176         
177         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
178                 BMO_SetFlag(bm, v, VERT_OLD);
179         }
180
181 #if 0
182         //a bit of cleaner code that, alas, doens't work.
183         /*build edge tags*/
184         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
185                 if (BMO_TestFlag(bm, e->v1, BEVEL_FLAG) || BMO_TestFlag(bm, e->v2, BEVEL_FLAG)) {
186                         BMIter liter;
187                         BMLoop *l;
188                         
189                         if (!BMO_TestFlag(bm, e, EDGE_OLD)) {
190                                 BMINDEX_SET(e, BLI_array_count(etags));
191                                 BLI_array_growone(etags);
192                                 
193                                 BMO_SetFlag(bm, e, EDGE_OLD);
194                         }
195                         
196                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_EDGE, e) {
197                                 BMLoop *l2;
198                                 BMIter liter2;
199                                 
200                                 if (BMO_TestFlag(bm, l->f, BEVEL_FLAG))
201                                         continue;
202                         
203                                 BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_FACE, l->f) {
204                                         BMINDEX_SET(l2, BLI_array_count(tags));
205                                         BLI_array_growone(tags);
206
207                                         if (!BMO_TestFlag(bm, l2->e, EDGE_OLD)) {
208                                                 BMINDEX_SET(l2->e, BLI_array_count(etags));
209                                                 BLI_array_growone(etags);
210                                                 
211                                                 BMO_SetFlag(bm, l2->e, EDGE_OLD);
212                                         }
213                                 }
214
215                                 BMO_SetFlag(bm, l->f, BEVEL_FLAG);
216                                 BLI_array_append(faces, l->f);
217                         }
218                 } else {
219                         BMINDEX_SET(e, -1);
220                 }
221         }
222 #endif
223         
224         /*create and assign looptag structures*/
225         BMO_ITER(e, &siter, bm, op, "geom", BM_EDGE) {
226                 BMLoop *l;
227                 BMIter liter;
228
229                 BMO_SetFlag(bm, e->v1, BEVEL_FLAG|BEVEL_DEL);
230                 BMO_SetFlag(bm, e->v2, BEVEL_FLAG|BEVEL_DEL);
231                 
232                 if (BM_Edge_FaceCount(e) < 2) {
233                         BMO_ClearFlag(bm, e, BEVEL_DEL);
234                         BMO_ClearFlag(bm, e->v1, BEVEL_DEL);
235                         BMO_ClearFlag(bm, e->v2, BEVEL_DEL);
236                         //continue;     
237                 }
238                 
239                 if (!BLI_smallhash_haskey(&hash, (intptr_t)e)) {
240                         BLI_array_growone(etags);
241                         BMINDEX_SET(e, BLI_array_count(etags)-1);
242                         BLI_smallhash_insert(&hash, (intptr_t)e, NULL);
243                         BMO_SetFlag(bm, e, EDGE_OLD);
244                 }
245                 
246                 /*find all faces surrounding e->v1 and, e->v2*/
247                 for (i=0; i<2; i++) {
248                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, i?e->v2:e->v1) {
249                                 BMLoop *l2;
250                                 BMIter liter2;
251                                 
252                                 /*see if we've already processed this loop's face*/
253                                 if (BLI_smallhash_haskey(&hash, (intptr_t)l->f))
254                                         continue;
255                                 
256                                 /*create tags for all loops in l->f*/
257                                 BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_FACE, l->f) {
258                                         BLI_array_growone(tags);
259                                         BMINDEX_SET(l2, BLI_array_count(tags)-1);
260                                         
261                                         if (!BLI_smallhash_haskey(&hash, (intptr_t)l2->e)) {
262                                                 BLI_array_growone(etags);
263                                                 BMINDEX_SET(l2->e, BLI_array_count(etags)-1);
264                                                 BLI_smallhash_insert(&hash, (intptr_t)l2->e, NULL);                                             
265                                                 BMO_SetFlag(bm, l2->e, EDGE_OLD);
266                                         }
267                                 }
268         
269                                 BLI_smallhash_insert(&hash, (intptr_t)l->f, NULL);
270                                 BMO_SetFlag(bm, l->f, BEVEL_FLAG);
271                                 BLI_array_append(faces, l->f);
272                         }
273                 }
274         }
275
276         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
277                 BMIter eiter;
278                 
279                 if (!BMO_TestFlag(bm, v, BEVEL_FLAG))
280                         continue;
281                 
282                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
283                         if (!BMO_TestFlag(bm, e, BEVEL_FLAG) && !ETAG_GET(e, v)) {
284                                 BMVert *v2;
285                                 float co[3];
286                                 
287                                 v2 = BM_OtherEdgeVert(e, v);
288                                 sub_v3_v3v3(co, v2->co, v->co);
289                                 mul_v3_fl(co, fac);
290                                 add_v3_v3(co, v->co);
291                                 
292                                 v2 = BM_Make_Vert(bm, co, v);
293                                 ETAG_SET(e, v, v2);
294                         }
295                 }
296         }
297         
298         for (i=0; i<BLI_array_count(faces); i++) {
299                 BMLoop *l;
300                 BMIter liter;
301                 
302                 BMO_SetFlag(bm, faces[i], FACE_OLD);
303                 
304                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, faces[i]) {
305                         float co[3];
306
307                         if (BMO_TestFlag(bm, l->e, BEVEL_FLAG)) {
308                                 if (BMO_TestFlag(bm, l->prev->e, BEVEL_FLAG))
309                                 {
310                                         tag = tags + BMINDEX_GET(l);
311                                         calc_corner_co(bm, l, co, fac);
312                                         tag->newv = BM_Make_Vert(bm, co, l->v);
313                                 } else {
314                                         tag = tags + BMINDEX_GET(l);
315                                         tag->newv = ETAG_GET(l->prev->e, l->v);
316                                         
317                                         if (!tag->newv) {
318                                                 sub_v3_v3v3(co, l->prev->v->co, l->v->co);
319                                                 mul_v3_fl(co, fac);
320                                                 add_v3_v3(co, l->v->co);
321                                         
322                                                 tag->newv = BM_Make_Vert(bm, co, l->v);
323                                                 
324                                                 ETAG_SET(l->prev->e, l->v, tag->newv);
325                                         }
326                                 }
327                         } else if (BMO_TestFlag(bm, l->v, BEVEL_FLAG)) {
328                                 tag = tags + BMINDEX_GET(l);
329                                 tag->newv = ETAG_GET(l->e, l->v);                               
330                 
331                                 if (!tag->newv) {
332                                         sub_v3_v3v3(co, l->next->v->co, l->v->co);
333                                         mul_v3_fl(co, fac);
334                                         add_v3_v3(co, l->v->co);
335                         
336                                         tag = tags + BMINDEX_GET(l);
337                                         tag->newv = BM_Make_Vert(bm, co, l->v);
338                                         
339                                         ETAG_SET(l->e, l->v, tag->newv);
340                                 }                                       
341                         } else {
342                                 tag = tags + BMINDEX_GET(l);
343                                 tag->newv = l->v;
344                                 BMO_ClearFlag(bm, l->v, BEVEL_DEL);
345                         }
346                 }
347         }
348         
349         /*create new faces*/
350         for (i=0; i<BLI_array_count(faces); i++) {
351                 BMLoop *l;
352                 BMIter liter;
353                 BMFace *f;
354                 int j;
355                 
356                 BMO_SetFlag(bm, faces[i], BEVEL_DEL);
357                 
358                 BLI_array_empty(verts);
359                 BLI_array_empty(edges);
360                 
361                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, faces[i]) {
362                         BMVert *v2;
363                         
364                         tag = tags + BMINDEX_GET(l);
365                         BLI_array_append(verts, tag->newv);
366                         
367                         etag = etags + BMINDEX_GET(l->e);
368                         v2 = l->next->v == l->e->v1 ? etag->newv1 : etag->newv2;
369                         
370                         tag = tags + BMINDEX_GET(l->next);
371                         if (!BMO_TestFlag(bm, l->e, BEVEL_FLAG) && v2 && v2 != tag->newv) {
372                                 BLI_array_append(verts, v2);
373                         }
374                 }
375                 
376                 for (j=0; j<BLI_array_count(verts); j++) {
377                         BMVert *next = verts[(j+1)%BLI_array_count(verts)];
378
379                         e = BM_Make_Edge(bm, next, verts[j], NULL, 1);
380                         BLI_array_append(edges, e);
381                 }
382                 
383                 f = BM_Make_Face(bm, verts, edges, BLI_array_count(verts));
384                 if (!f) {
385                         printf("eck!!\n");
386                         continue;
387                 }
388                         
389                 BMO_SetFlag(bm, f, FACE_NEW);
390                 
391                 /*create quad spans between split edges*/
392                 BMO_SetFlag(bm, f, FACE_NEW);
393                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, faces[i]) {
394                         BMVert *v1=NULL, *v2=NULL, *v3=NULL, *v4=NULL;
395                         
396                         if (!BMO_TestFlag(bm, l->e, BEVEL_FLAG))
397                                 continue;
398                         
399                         v1 = tags[BMINDEX_GET(l)].newv;
400                         v2 = tags[BMINDEX_GET(l->next)].newv;
401                         if (l->radial_next != l) {
402                                 v3 = tags[BMINDEX_GET(l->radial_next)].newv;
403                                 if (l->radial_next->next->v == l->next->v) {
404                                         v4 = v3;
405                                         v3 = tags[BMINDEX_GET(l->radial_next->next)].newv;
406                                 } else {
407                                         v4 = tags[BMINDEX_GET(l->radial_next->next)].newv;
408                                 }
409                         } else {
410                                 v3 = l->next->v;
411                                 v4 = l->v;
412                                 
413                                 for (j=0; j<2; j++) {
414                                         BMIter eiter;
415                                         BMVert *v = j ? v4 : v3;
416
417                                         BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
418                                                 if (!BM_Vert_In_Edge(e, v3) || !BM_Vert_In_Edge(e, v4))
419                                                         continue;
420                                                 
421                                                 if (!BMO_TestFlag(bm, e, BEVEL_FLAG) && BMO_TestFlag(bm, e, EDGE_OLD)) {
422                                                         BMVert *vv;
423                                                         
424                                                         vv = ETAG_GET(e, v);
425                                                         if (!vv || BMO_TestFlag(bm, vv, BEVEL_FLAG))
426                                                                 continue;
427                                                         
428                                                         if (j)
429                                                                 v1 = vv;
430                                                         else
431                                                                 v2 = vv;
432                                                         break;
433                                                 }
434                                         }
435                                 }
436
437                                 BMO_ClearFlag(bm, v3, BEVEL_DEL);
438                                 BMO_ClearFlag(bm, v4, BEVEL_DEL);
439                         }
440                         
441                         if (v1 != v2 && v2 != v3 && v3 != v4) {
442                                 BMIter liter2;
443                                 BMLoop *l2;
444                                 
445                                 f = BM_Make_QuadTri(bm, v4, v3, v2, v1, l->f, 1);
446                                 if (!f) {
447                                         printf("eek!\n");
448                                         continue;
449                                 }
450                                 
451                                 BMO_SetFlag(bm, f, FACE_NEW|FACE_SPAN);
452                                 
453                                 /*un-tag edges in f for deletion*/
454                                 BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_FACE, f) {
455                                         BMO_ClearFlag(bm, l2->e, BEVEL_DEL);
456                                 }
457                         } else {
458                                 f = NULL;
459                         }
460                 }       
461         }
462         
463         /*fill in holes at vertices*/
464         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
465                 BMIter eiter;
466                 BMVert *vv, *vstart=NULL, *lastv=NULL;
467                 SmallHash tmphash;
468                 int rad, insorig=0, err=0;
469                 
470                 BLI_smallhash_init(&tmphash);
471                 
472                 if (!BMO_TestFlag(bm, v, BEVEL_FLAG))
473                         continue;
474                 
475                 BLI_array_empty(verts);
476                 BLI_array_empty(edges);
477                 
478                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
479                         BMIter liter;
480                         BMVert *v1=NULL, *v2=NULL;
481                         BMLoop *l;
482                         
483                         if (BM_Edge_FaceCount(e) < 2)
484                                 insorig = 1;
485                         
486                         rad = 0;
487                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_EDGE, e) {
488                                 if (!BMO_TestFlag(bm, l->f, FACE_OLD))
489                                         continue;
490                                 
491                                 rad++;
492                                 
493                                 if (l->v == v)
494                                         tag = tags + BMINDEX_GET(l);
495                                 else
496                                         tag = tags + BMINDEX_GET(l->next);
497                                 
498                                 if (!v1)
499                                         v1 = tag->newv;
500                                 else if (!v2);
501                                         v2 = tag->newv;
502                         }
503                         
504                         if (rad < 2)
505                                 insorig = 1;
506                         
507                         if (!v1)
508                                 v1 = ETAG_GET(e, v);
509                         if (!v2 || v1 == v2)
510                                 v2 = ETAG_GET(e, v);
511                         
512                         if (v1) {
513                                 if (!BLI_smallhash_haskey(&tmphash, (intptr_t)v1)) {
514                                         BLI_array_append(verts, v1);
515                                         BLI_smallhash_insert(&tmphash, (intptr_t)v1, NULL);
516                                 }
517                                 
518                                 if (v2 && v1 != v2 && !BLI_smallhash_haskey(&tmphash, (intptr_t)v2)) {
519                                         BLI_array_append(verts, v2);
520                                         BLI_smallhash_insert(&tmphash, (intptr_t)v2, NULL);
521                                 }
522                         }
523                 }
524                 
525                 if (!BLI_array_count(verts))
526                         continue;
527                 
528                 if (insorig) {
529                         BLI_array_append(verts, v);
530                         BLI_smallhash_insert(&tmphash, (intptr_t)v, NULL);
531                 }
532                 
533                 /*find edges that exist between vertices in verts.  this is basically
534           a topological walk of the edges connecting them.*/
535                 vstart = vstart ? vstart : verts[0];
536                 vv = vstart;
537                 do {
538                         BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, vv) {
539                                 BMVert *vv2 = BM_OtherEdgeVert(e, vv);
540                                 
541                                 if (vv2 != lastv && BLI_smallhash_haskey(&tmphash, (intptr_t)vv2)) {
542                                         /*if we've go over the same vert twice, break out of outer loop*/
543                                         if (BLI_smallhash_lookup(&tmphash, (intptr_t)vv2) != NULL) {
544                                                 e = NULL;
545                                                 err = 1;
546                                                 break;
547                                         }
548                                         
549                                         /*use self pointer as tag*/
550                                         BLI_smallhash_remove(&tmphash, (intptr_t)vv2);
551                                         BLI_smallhash_insert(&tmphash, (intptr_t)vv2, vv2);
552                                         
553                                         lastv = vv;
554                                         BLI_array_append(edges, e);
555                                         vv = vv2;
556                                         break;
557                                 }
558                         }
559                         if (e == NULL)
560                                 break;
561                 } while (vv != vstart);
562                 
563                 if (err)
564                         continue;
565                 
566                 /*there may not be a complete loop of edges, so start again and make
567           final edge afterwards.  in this case, the previous loop worked to
568           find one of the two edges at the extremes.*/
569                 if (vv != vstart) {
570                         /*undo previous tagging*/
571                         for (i=0; i<BLI_array_count(verts); i++) {
572                                 BLI_smallhash_remove(&tmphash, (intptr_t)verts[i]);
573                                 BLI_smallhash_insert(&tmphash, (intptr_t)verts[i], NULL);
574                         }
575
576                         vstart = vv;
577                         lastv = NULL;
578                         BLI_array_empty(edges);
579                         do {
580                                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, vv) {
581                                         BMVert *vv2 = BM_OtherEdgeVert(e, vv);
582                                         
583                                         if (vv2 != lastv && BLI_smallhash_haskey(&tmphash, (intptr_t)vv2)) {
584                                                 /*if we've go over the same vert twice, break out of outer loop*/
585                                                 if (BLI_smallhash_lookup(&tmphash, (intptr_t)vv2) != NULL) {
586                                                         e = NULL;
587                                                         err = 1;
588                                                         break;
589                                                 }
590                                                 
591                                                 /*use self pointer as tag*/
592                                                 BLI_smallhash_remove(&tmphash, (intptr_t)vv2);
593                                                 BLI_smallhash_insert(&tmphash, (intptr_t)vv2, vv2);
594                                                 
595                                                 lastv = vv;
596                                                 BLI_array_append(edges, e);
597                                                 vv = vv2;
598                                                 break;
599                                         }
600                                 }
601                                 if (e == NULL)
602                                         break;
603                         } while (vv != vstart);
604                         
605                         if (!err) {
606                                 e = BM_Make_Edge(bm, vv, vstart, NULL, 1);
607                                 BLI_array_append(edges, e);
608                         }
609                 }
610                 
611                 if (err)
612                         continue;
613                 
614                 if (BLI_array_count(edges) >= 3) {
615                         BMFace *f;
616                         
617                         f = BM_Make_Ngon(bm, lastv, vstart, edges, BLI_array_count(edges), 0);
618                         if (!f) {
619                                 printf("eek! in bevel vert fill!\n");
620                         } else 
621                                 BMO_SetFlag(bm, f, FACE_NEW|FACE_HOLE);
622                 }
623                 BLI_smallhash_release(&tmphash);
624         }
625         
626         /*copy over customdata*/
627         for (i=0; i<BLI_array_count(faces); i++) {
628                 BMLoop *l;
629                 BMIter liter;
630                 BMFace *f = faces[i];
631                 
632                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
633                         BMLoop *l2;
634                         BMIter liter2;
635                         
636                         tag = tags + BMINDEX_GET(l);
637                         if (!tag->newv)
638                                 continue;
639                         
640                         BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_VERT, tag->newv) {
641                                 if (!BMO_TestFlag(bm, l2->f, FACE_NEW) || (l2->v != tag->newv && l2->v != l->v))
642                                         continue;
643                                 
644                                 if (tag->newv != l->v) {
645                                         BM_Copy_Attributes(bm, bm, l->f, l2->f);
646                                         BM_loop_interp_from_face(bm, l2, f);
647                                 } else {
648                                         BM_Copy_Attributes(bm, bm, l->f, l2->f);
649                                         BM_Copy_Attributes(bm, bm, l, l2);
650                                 }
651                         }
652                 }
653         }
654         
655         /*handle vertices along boundary edges*/
656         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
657                 if (BMO_TestFlag(bm, v, VERT_OLD) && BMO_TestFlag(bm, v, BEVEL_FLAG) && !BMO_TestFlag(bm, v, BEVEL_DEL)) {
658                         BMLoop *l;
659                         BMLoop *lorig=NULL;
660                         BMIter liter;
661                         
662                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, v) {
663                                 BMIter liter2;
664                                 BMLoop *l2 = l->v == v ? l : l->next, *l3;
665                                 
666                                 if (BMO_TestFlag(bm, l->f, FACE_OLD)) {
667                                         lorig = l;
668                                         break;
669                                 }
670                         }
671                         
672                         if (!lorig)
673                                 continue;
674                         
675                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, v) {
676                                 BMLoop *l2 = l->v == v ? l : l->next, *l3;
677                                 
678                                 BM_Copy_Attributes(bm, bm, lorig->f, l2->f);
679                                 BM_Copy_Attributes(bm, bm, lorig, l2);
680                         }
681                 }
682         }
683
684         BMO_CallOpf(bm, "del geom=%fv context=%i", BEVEL_DEL, DEL_VERTS);
685
686         /*clean up any edges that might not get properly deleted*/
687         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
688                 if (BMO_TestFlag(bm, e, EDGE_OLD) && !e->l)
689                         BMO_SetFlag(bm, e, BEVEL_DEL);
690         }
691
692         BMO_CallOpf(bm, "del geom=%fe context=%i", BEVEL_DEL, DEL_EDGES);
693         BMO_CallOpf(bm, "del geom=%ff context=%i", BEVEL_DEL, DEL_FACES);
694         
695         BLI_smallhash_release(&hash);
696         BLI_array_free(tags);
697         BLI_array_free(etags);
698         BLI_array_free(verts);
699         BLI_array_free(edges);
700         BLI_array_free(faces);
701         
702         BMO_Flag_To_Slot(bm, op, "face_spans", FACE_SPAN, BM_FACE);
703         BMO_Flag_To_Slot(bm, op, "face_holes", FACE_HOLE, BM_FACE);
704 }