remove unused vars
[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                 int j;
447                 
448                 /*create quad spans between split edges*/
449                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, faces[i]) {
450                         BMVert *v1=NULL, *v2=NULL, *v3=NULL, *v4=NULL;
451                         
452                         if (!BMO_TestFlag(bm, l->e, BEVEL_FLAG))
453                                 continue;
454                         
455                         v1 = tags[BM_GetIndex(l)].newv;
456                         v2 = tags[BM_GetIndex(l->next)].newv;
457                         if (l->radial_next != l) {
458                                 v3 = tags[BM_GetIndex(l->radial_next)].newv;
459                                 if (l->radial_next->next->v == l->next->v) {
460                                         v4 = v3;
461                                         v3 = tags[BM_GetIndex(l->radial_next->next)].newv;
462                                 } else {
463                                         v4 = tags[BM_GetIndex(l->radial_next->next)].newv;
464                                 }
465                         } else {
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                                         float ang;
513                                         
514                                         e1 = BM_Edge_Exist(v1, v4);
515                                         e2 = BM_Edge_Exist(v2, v3);
516                                         
517                                         if (l->radial_next->v == l->v) {
518                                                 l2 = l->radial_next->prev;
519                                                 l3 = l->radial_next->next;
520                                         } else {
521                                                 l2 = l->radial_next->next;
522                                                 l3 = l->radial_next->prev;
523                                         }
524                                         
525                                         d3 = CustomData_bmesh_get_n(&bm->edata, e1->head.data, CD_PROP_FLT, li);
526                                         d1 = *(float*)CustomData_bmesh_get_n(&bm->edata, l->prev->e->head.data, CD_PROP_FLT, li);
527                                         d2 = *(float*)CustomData_bmesh_get_n(&bm->edata, l2->e->head.data, CD_PROP_FLT, li);
528                                         
529                                         ang = angle_v3v3v3(l->prev->v->co, l->v->co, BM_OtherEdgeVert(l2->e, l->v)->co);
530                                         *d3 = (d1+d2)*0.5;
531                                         
532                                         d3 = CustomData_bmesh_get_n(&bm->edata, e2->head.data, CD_PROP_FLT, li);
533                                         d1 = *(float*)CustomData_bmesh_get_n(&bm->edata, l->next->e->head.data, CD_PROP_FLT, li);
534                                         d2 = *(float*)CustomData_bmesh_get_n(&bm->edata, l3->e->head.data, CD_PROP_FLT, li);
535
536                                         ang = angle_v3v3v3(BM_OtherEdgeVert(l->next->e, l->next->v)->co, l->next->v->co, BM_OtherEdgeVert(l3->e, l->next->v)->co);
537                                         *d3 = (d1+d2)*0.5;
538                                 }
539
540                                 if (!f) {
541                                         printf("eek!\n");
542                                         continue;
543                                 }
544                                 
545                                 BMO_SetFlag(bm, f, FACE_NEW|FACE_SPAN);
546                                 
547                                 /*un-tag edges in f for deletion*/
548                                 BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_FACE, f) {
549                                         BMO_ClearFlag(bm, l2->e, BEVEL_DEL);
550                                 }
551                         } else {
552                                 f = NULL;
553                         }
554                 }       
555         }
556         
557         /*fill in holes at vertices*/
558         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
559                 BMIter eiter;
560                 BMVert *vv, *vstart=NULL, *lastv=NULL;
561                 SmallHash tmphash;
562                 int rad, insorig=0, err=0;
563                 
564                 BLI_smallhash_init(&tmphash);
565                 
566                 if (!BMO_TestFlag(bm, v, BEVEL_FLAG))
567                         continue;
568                 
569                 BLI_array_empty(verts);
570                 BLI_array_empty(edges);
571                 
572                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
573                         BMIter liter;
574                         BMVert *v1=NULL, *v2=NULL;
575                         BMLoop *l;
576                         
577                         if (BM_Edge_FaceCount(e) < 2)
578                                 insorig = 1;
579                         
580                         rad = 0;
581                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_EDGE, e) {
582                                 if (!BMO_TestFlag(bm, l->f, FACE_OLD))
583                                         continue;
584                                 
585                                 rad++;
586                                 
587                                 if (l->v == v)
588                                         tag = tags + BM_GetIndex(l);
589                                 else
590                                         tag = tags + BM_GetIndex(l->next);
591                                 
592                                 if (!v1)
593                                         v1 = tag->newv;
594                                 else if (!v2);
595                                         v2 = tag->newv;
596                         }
597                         
598                         if (rad < 2)
599                                 insorig = 1;
600                         
601                         if (!v1)
602                                 v1 = ETAG_GET(e, v);
603                         if (!v2 || v1 == v2)
604                                 v2 = ETAG_GET(e, v);
605                         
606                         if (v1) {
607                                 if (!BLI_smallhash_haskey(&tmphash, (intptr_t)v1)) {
608                                         BLI_array_append(verts, v1);
609                                         BLI_smallhash_insert(&tmphash, (intptr_t)v1, NULL);
610                                 }
611                                 
612                                 if (v2 && v1 != v2 && !BLI_smallhash_haskey(&tmphash, (intptr_t)v2)) {
613                                         BLI_array_append(verts, v2);
614                                         BLI_smallhash_insert(&tmphash, (intptr_t)v2, NULL);
615                                 }
616                         }
617                 }
618                 
619                 if (!BLI_array_count(verts))
620                         continue;
621                 
622                 if (insorig) {
623                         BLI_array_append(verts, v);
624                         BLI_smallhash_insert(&tmphash, (intptr_t)v, NULL);
625                 }
626                 
627                 /*find edges that exist between vertices in verts.  this is basically
628           a topological walk of the edges connecting them.*/
629                 vstart = vstart ? vstart : verts[0];
630                 vv = vstart;
631                 do {
632                         BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, vv) {
633                                 BMVert *vv2 = BM_OtherEdgeVert(e, vv);
634                                 
635                                 if (vv2 != lastv && BLI_smallhash_haskey(&tmphash, (intptr_t)vv2)) {
636                                         /*if we've go over the same vert twice, break out of outer loop*/
637                                         if (BLI_smallhash_lookup(&tmphash, (intptr_t)vv2) != NULL) {
638                                                 e = NULL;
639                                                 err = 1;
640                                                 break;
641                                         }
642                                         
643                                         /*use self pointer as tag*/
644                                         BLI_smallhash_remove(&tmphash, (intptr_t)vv2);
645                                         BLI_smallhash_insert(&tmphash, (intptr_t)vv2, vv2);
646                                         
647                                         lastv = vv;
648                                         BLI_array_append(edges, e);
649                                         vv = vv2;
650                                         break;
651                                 }
652                         }
653                         if (e == NULL)
654                                 break;
655                 } while (vv != vstart);
656                 
657                 if (err)
658                         continue;
659                 
660                 /*there may not be a complete loop of edges, so start again and make
661           final edge afterwards.  in this case, the previous loop worked to
662           find one of the two edges at the extremes.*/
663                 if (vv != vstart) {
664                         /*undo previous tagging*/
665                         for (i=0; i<BLI_array_count(verts); i++) {
666                                 BLI_smallhash_remove(&tmphash, (intptr_t)verts[i]);
667                                 BLI_smallhash_insert(&tmphash, (intptr_t)verts[i], NULL);
668                         }
669
670                         vstart = vv;
671                         lastv = NULL;
672                         BLI_array_empty(edges);
673                         do {
674                                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, vv) {
675                                         BMVert *vv2 = BM_OtherEdgeVert(e, vv);
676                                         
677                                         if (vv2 != lastv && BLI_smallhash_haskey(&tmphash, (intptr_t)vv2)) {
678                                                 /*if we've go over the same vert twice, break out of outer loop*/
679                                                 if (BLI_smallhash_lookup(&tmphash, (intptr_t)vv2) != NULL) {
680                                                         e = NULL;
681                                                         err = 1;
682                                                         break;
683                                                 }
684                                                 
685                                                 /*use self pointer as tag*/
686                                                 BLI_smallhash_remove(&tmphash, (intptr_t)vv2);
687                                                 BLI_smallhash_insert(&tmphash, (intptr_t)vv2, vv2);
688                                                 
689                                                 lastv = vv;
690                                                 BLI_array_append(edges, e);
691                                                 vv = vv2;
692                                                 break;
693                                         }
694                                 }
695                                 if (e == NULL)
696                                         break;
697                         } while (vv != vstart);
698                         
699                         if (!err) {
700                                 e = BM_Make_Edge(bm, vv, vstart, NULL, 1);
701                                 BLI_array_append(edges, e);
702                         }
703                 }
704                 
705                 if (err)
706                         continue;
707                 
708                 if (BLI_array_count(edges) >= 3) {
709                         BMFace *f;
710                         
711                         if (BM_Face_Exists(bm, verts, BLI_array_count(verts), &f))
712                                 continue;
713                         
714                         f = BM_Make_Ngon(bm, lastv, vstart, edges, BLI_array_count(edges), 0);
715                         if (!f) {
716                                 printf("eek! in bevel vert fill!\n");
717                         } else 
718                                 BMO_SetFlag(bm, f, FACE_NEW|FACE_HOLE);
719                 }
720                 BLI_smallhash_release(&tmphash);
721         }
722         
723         /*copy over customdata*/
724         for (i=0; i<BLI_array_count(faces); i++) {
725                 BMLoop *l;
726                 BMIter liter;
727                 BMFace *f = faces[i];
728                 
729                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
730                         BMLoop *l2;
731                         BMIter liter2;
732                         
733                         tag = tags + BM_GetIndex(l);
734                         if (!tag->newv)
735                                 continue;
736                         
737                         BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_VERT, tag->newv) {
738                                 if (!BMO_TestFlag(bm, l2->f, FACE_NEW) || (l2->v != tag->newv && l2->v != l->v))
739                                         continue;
740                                 
741                                 if (tag->newv != l->v || HasMDisps) {
742                                         BM_Copy_Attributes(bm, bm, l->f, l2->f);
743                                         BM_loop_interp_from_face(bm, l2, l->f, 1, 1);
744                                 } else {
745                                         BM_Copy_Attributes(bm, bm, l->f, l2->f);
746                                         BM_Copy_Attributes(bm, bm, l, l2);
747                                 }
748                                 
749                                 if (HasMDisps) {
750                                         BMLoop *l3;
751                                         BMIter liter3;
752                                         
753                                         BM_ITER(l3, &liter3, bm, BM_LOOPS_OF_FACE, l2->f) {
754                                                 BM_loop_interp_multires(bm, l3, l->f);
755                                         }
756                                 }
757                         }
758                 }
759         }
760         
761         /*handle vertices along boundary edges*/
762         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
763                 if (BMO_TestFlag(bm, v, VERT_OLD) && BMO_TestFlag(bm, v, BEVEL_FLAG) && !BMO_TestFlag(bm, v, BEVEL_DEL)) {
764                         BMLoop *l;
765                         BMLoop *lorig=NULL;
766                         BMIter liter;
767                         
768                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, v) {
769                                 // BMIter liter2;
770                                 // BMLoop *l2 = l->v == v ? l : l->next, *l3;
771                                 
772                                 if (BMO_TestFlag(bm, l->f, FACE_OLD)) {
773                                         lorig = l;
774                                         break;
775                                 }
776                         }
777                         
778                         if (!lorig)
779                                 continue;
780                         
781                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, v) {
782                                 BMLoop *l2 = l->v == v ? l : l->next;
783                                 
784                                 BM_Copy_Attributes(bm, bm, lorig->f, l2->f);
785                                 BM_Copy_Attributes(bm, bm, lorig, l2);
786                         }
787                 }
788         }
789 #if 0
790         /*clean up any remainin 2-edged faces*/
791         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
792                 if (f->len == 2) {
793                         BMFace *faces[2] = {f, bm_firstfaceloop(f)->radial_next->f};
794                         
795                         if (faces[0] == faces[1])
796                                 BM_Kill_Face(bm, f);
797                         else
798                                 BM_Join_Faces(bm, faces, 2);
799                 }
800         }
801 #endif
802         
803         BMO_CallOpf(bm, "del geom=%fv context=%i", BEVEL_DEL, DEL_VERTS);
804
805         /*clean up any edges that might not get properly deleted*/
806         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
807                 if (BMO_TestFlag(bm, e, EDGE_OLD) && !e->l)
808                         BMO_SetFlag(bm, e, BEVEL_DEL);
809         }
810
811         BMO_CallOpf(bm, "del geom=%fe context=%i", BEVEL_DEL, DEL_EDGES);
812         BMO_CallOpf(bm, "del geom=%ff context=%i", BEVEL_DEL, DEL_FACES);
813         
814         BLI_smallhash_release(&hash);
815         BLI_array_free(tags);
816         BLI_array_free(etags);
817         BLI_array_free(verts);
818         BLI_array_free(edges);
819         BLI_array_free(faces);
820         
821         BMO_Flag_To_Slot(bm, op, "face_spans", FACE_SPAN, BM_FACE);
822         BMO_Flag_To_Slot(bm, op, "face_holes", FACE_HOLE, BM_FACE);
823 }