abc4cd52198e0a8d81dc385871cac98bb37fc4d9
[blender.git] / source / blender / bmesh / operators / bevel.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * Contributor(s): Joseph Eagar.
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 #include "MEM_guardedalloc.h"
24
25 #include "BLI_utildefines.h"
26 #include "BLI_ghash.h"
27 #include "BLI_memarena.h"
28 #include "BLI_array.h"
29 #include "BLI_math.h"
30 #include "BLI_array.h"
31 #include "BLI_utildefines.h"
32 #include "BLI_smallhash.h"
33
34 #include "bmesh.h"
35 #include "bmesh_operators_private.h"
36
37 #define BEVEL_FLAG      1
38 #define BEVEL_DEL       2
39 #define FACE_NEW        4
40 #define EDGE_OLD        8
41 #define FACE_OLD        16
42 #define FACE_DONE       32
43 #define VERT_OLD        64
44 #define FACE_SPAN       128
45 #define FACE_HOLE       256
46
47 typedef struct LoopTag {
48         BMVert *newv;
49 } LoopTag;
50
51 typedef struct EdgeTag {
52         BMVert *newv1, *newv2;
53 } EdgeTag;
54
55 static void calc_corner_co(BMesh *bm, BMLoop *l, const float fac, float r_co[3],
56                            const short do_dist, const short do_even)
57 {
58         float  no[3], l_vec_prev[3], l_vec_next[3], l_co_prev[3], l_co[3], l_co_next[3], co_ofs[3];
59         int is_concave;
60
61         /* first get the prev/next verts */
62         if (l->f->len > 2) {
63                 copy_v3_v3(l_co_prev, l->prev->v->co);
64                 copy_v3_v3(l_co, l->v->co);
65                 copy_v3_v3(l_co_next, l->next->v->co);
66
67                 /* calculate norma */
68                 sub_v3_v3v3(l_vec_prev, l_co_prev, l_co);
69                 sub_v3_v3v3(l_vec_next, l_co_next, l_co);
70
71                 cross_v3_v3v3(no, l_vec_prev, l_vec_next);
72                 is_concave = dot_v3v3(no, l->f->no) > 0.0f;
73         }
74         else {
75                 BMIter iter;
76                 BMLoop *l2;
77                 float up[3] = {0.0f, 0.0f, 1.0f};
78
79                 copy_v3_v3(l_co_prev, l->prev->v->co);
80                 copy_v3_v3(l_co, l->v->co);
81                 
82                 BM_ITER(l2, &iter, bm, BM_LOOPS_OF_VERT, l->v) {
83                         if (l2->f != l->f) {
84                                 copy_v3_v3(l_co_next, BM_OtherEdgeVert(l2->e, l2->next->v)->co);
85                                 break;
86                         }
87                 }
88                 
89                 sub_v3_v3v3(l_vec_prev, l_co_prev, l_co);
90                 sub_v3_v3v3(l_vec_next, l_co_next, l_co);
91
92                 cross_v3_v3v3(no, l_vec_prev, l_vec_next);
93                 if (dot_v3v3(no, no) == 0.0f) {
94                         no[0] = no[1] = 0.0f; no[2] = -1.0f;    
95                 }
96                 
97                 is_concave = dot_v3v3(no, up) < 0.0f;
98         }
99
100
101         /* now calculate the new location */
102         if (do_dist) { /* treat 'fac' as distance */
103
104                 normalize_v3(l_vec_prev);
105                 normalize_v3(l_vec_next);
106
107                 add_v3_v3v3(co_ofs, l_vec_prev, l_vec_next);
108                 normalize_v3(co_ofs);
109
110                 if (do_even) {
111                         negate_v3(l_vec_next);
112                         mul_v3_fl(co_ofs, fac * shell_angle_to_dist(0.5f * angle_normalized_v3v3(l_vec_prev, l_vec_next)));
113                         /* negate_v3(l_vec_next); */ /* no need unless we use again */
114                 }
115                 else {
116                         mul_v3_fl(co_ofs, fac);
117                 }
118         }
119         else { /* treat as 'fac' as a factor (0 - 1) */
120
121                 /* not strictly necessary, balance vectors
122                  * so the longer edge doesn't skew the result,
123                  * gives nicer, move even output.
124                  *
125                  * Use the minimum rather then the middle value so skinny faces don't flip along the short axis */
126                 float min_fac = minf(normalize_v3(l_vec_prev), normalize_v3(l_vec_next));
127                 float angle = do_even ? angle_normalized_v3v3(l_vec_prev, l_vec_next) : 0.0f; /* get angle while normalized */
128
129                 mul_v3_fl(l_vec_prev, min_fac);
130                 mul_v3_fl(l_vec_next, min_fac);
131
132                 add_v3_v3v3(co_ofs, l_vec_prev, l_vec_next);
133
134                 /* done */
135                 if (do_even) {
136                         negate_v3(l_vec_next);
137                         mul_v3_fl(co_ofs, (fac * 0.5) * shell_angle_to_dist(0.5f * angle));
138                         /* negate_v3(l_vec_next); */ /* no need unless we use again */
139                 }
140                 else {
141                         mul_v3_fl(co_ofs, fac * 0.5);
142                 }
143         }
144
145         /* apply delta vec */
146         if (is_concave)
147                 negate_v3(co_ofs);
148
149         add_v3_v3v3(r_co, co_ofs, l->v->co);
150 }
151
152
153 #define ETAG_SET(e, v, nv)  (                                                 \
154         (v) == (e)->v1 ?                                                          \
155                 (etags[BM_GetIndex((e))].newv1 = (nv)) :                              \
156                 (etags[BM_GetIndex((e))].newv2 = (nv))                                \
157         )
158
159 #define ETAG_GET(e, v)  (                                                     \
160         (v) == (e)->v1 ?                                                          \
161                 (etags[BM_GetIndex((e))].newv1) :                                     \
162                 (etags[BM_GetIndex((e))].newv2)                                       \
163         )
164
165 void bmesh_bevel_exec(BMesh *bm, BMOperator *op)
166 {
167         BMOIter siter;
168         BMIter iter;
169         BMEdge *e;
170         BMVert *v;
171         BMFace **faces = NULL, *f;
172         LoopTag *tags = NULL, *tag;
173         EdgeTag *etags = NULL;
174         BMVert **verts = NULL;
175         BMEdge **edges = NULL;
176         BLI_array_declare(faces);
177         BLI_array_declare(tags);
178         BLI_array_declare(etags);
179         BLI_array_declare(verts);
180         BLI_array_declare(edges);
181         SmallHash hash;
182         float fac = BMO_Get_Float(op, "percent");
183         const short do_even = BMO_Get_Int(op, "use_even");
184         const short do_dist = BMO_Get_Int(op, "use_dist");
185         int i, li, has_elens, HasMDisps = CustomData_has_layer(&bm->ldata, CD_MDISPS);
186         
187         has_elens = CustomData_has_layer(&bm->edata, CD_PROP_FLT) && BMO_Get_Int(op, "use_lengths");
188         if (has_elens) {
189                 li = BMO_Get_Int(op, "lengthlayer");
190         }
191         
192         BLI_smallhash_init(&hash);
193         
194         BMO_ITER(e, &siter, bm, op, "geom", BM_EDGE) {
195                 BMO_SetFlag(bm, e, BEVEL_FLAG|BEVEL_DEL);
196                 BMO_SetFlag(bm, e->v1, BEVEL_FLAG|BEVEL_DEL);
197                 BMO_SetFlag(bm, e->v2, BEVEL_FLAG|BEVEL_DEL);
198                 
199                 if (BM_Edge_FaceCount(e) < 2) {
200                         BMO_ClearFlag(bm, e, BEVEL_DEL);
201                         BMO_ClearFlag(bm, e->v1, BEVEL_DEL);
202                         BMO_ClearFlag(bm, e->v2, BEVEL_DEL);
203                 }
204 #if 0
205                 if (BM_Edge_FaceCount(e) == 0) {
206                         BMVert *verts[2] = {e->v1, e->v2};
207                         BMEdge *edges[2] = {e, BM_Make_Edge(bm, e->v1, e->v2, e, 0)};
208                         
209                         BMO_SetFlag(bm, edges[1], BEVEL_FLAG);
210                         BM_Make_Face(bm, verts, edges, 2, 0);
211                 }
212 #endif
213         }
214         
215         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
216                 BMO_SetFlag(bm, v, VERT_OLD);
217         }
218
219 #if 0
220         //a bit of cleaner code that, alas, doens't work.
221         /* build edge tag */
222         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
223                 if (BMO_TestFlag(bm, e->v1, BEVEL_FLAG) || BMO_TestFlag(bm, e->v2, BEVEL_FLAG)) {
224                         BMIter liter;
225                         BMLoop *l;
226                         
227                         if (!BMO_TestFlag(bm, e, EDGE_OLD)) {
228                                 BM_SetIndex(e, BLI_array_count(etags)); /* set_dirty! */
229                                 BLI_array_growone(etags);
230                                 
231                                 BMO_SetFlag(bm, e, EDGE_OLD);
232                         }
233                         
234                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_EDGE, e) {
235                                 BMLoop *l2;
236                                 BMIter liter2;
237                                 
238                                 if (BMO_TestFlag(bm, l->f, BEVEL_FLAG))
239                                         continue;
240                         
241                                 BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_FACE, l->f) {
242                                         BM_SetIndex(l2, BLI_array_count(tags)); /* set_loop */
243                                         BLI_array_growone(tags);
244
245                                         if (!BMO_TestFlag(bm, l2->e, EDGE_OLD)) {
246                                                 BM_SetIndex(l2->e, BLI_array_count(etags)); /* set_dirty! */
247                                                 BLI_array_growone(etags);
248                                                 
249                                                 BMO_SetFlag(bm, l2->e, EDGE_OLD);
250                                         }
251                                 }
252
253                                 BMO_SetFlag(bm, l->f, BEVEL_FLAG);
254                                 BLI_array_append(faces, l->f);
255                         }
256                 }
257                 else {
258                         BM_SetIndex(e, -1); /* set_dirty! */
259                 }
260         }
261 #endif
262         
263         /* create and assign looptag structure */
264         BMO_ITER(e, &siter, bm, op, "geom", BM_EDGE) {
265                 BMLoop *l;
266                 BMIter liter;
267
268                 BMO_SetFlag(bm, e->v1, BEVEL_FLAG|BEVEL_DEL);
269                 BMO_SetFlag(bm, e->v2, BEVEL_FLAG|BEVEL_DEL);
270                 
271                 if (BM_Edge_FaceCount(e) < 2) {
272                         BMO_ClearFlag(bm, e, BEVEL_DEL);
273                         BMO_ClearFlag(bm, e->v1, BEVEL_DEL);
274                         BMO_ClearFlag(bm, e->v2, BEVEL_DEL);
275                 }
276                 
277                 if (!BLI_smallhash_haskey(&hash, (intptr_t)e)) {
278                         BLI_array_growone(etags);
279                         BM_SetIndex(e, BLI_array_count(etags) - 1); /* set_dirty! */
280                         BLI_smallhash_insert(&hash, (intptr_t)e, NULL);
281                         BMO_SetFlag(bm, e, EDGE_OLD);
282                 }
283                 
284                 /* find all faces surrounding e->v1 and, e->v2 */
285                 for (i = 0; i < 2; i++) {
286                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, i ? e->v2:e->v1) {
287                                 BMLoop *l2;
288                                 BMIter liter2;
289                                 
290                                 /* see if we've already processed this loop's fac */
291                                 if (BLI_smallhash_haskey(&hash, (intptr_t)l->f))
292                                         continue;
293                                 
294                                 /* create tags for all loops in l-> */
295                                 BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_FACE, l->f) {
296                                         BLI_array_growone(tags);
297                                         BM_SetIndex(l2, BLI_array_count(tags) - 1); /* set_loop */
298                                         
299                                         if (!BLI_smallhash_haskey(&hash, (intptr_t)l2->e)) {
300                                                 BLI_array_growone(etags);
301                                                 BM_SetIndex(l2->e, BLI_array_count(etags) - 1); /* set_dirty! */
302                                                 BLI_smallhash_insert(&hash, (intptr_t)l2->e, NULL);                                             
303                                                 BMO_SetFlag(bm, l2->e, EDGE_OLD);
304                                         }
305                                 }
306         
307                                 BLI_smallhash_insert(&hash, (intptr_t)l->f, NULL);
308                                 BMO_SetFlag(bm, l->f, BEVEL_FLAG);
309                                 BLI_array_append(faces, l->f);
310                         }
311                 }
312         }
313
314         bm->elem_index_dirty |= BM_EDGE;
315         
316         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
317                 BMIter eiter;
318                 
319                 if (!BMO_TestFlag(bm, v, BEVEL_FLAG))
320                         continue;
321                 
322                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
323                         if (!BMO_TestFlag(bm, e, BEVEL_FLAG) && !ETAG_GET(e, v)) {
324                                 BMVert *v2;
325                                 float co[3];
326                                 
327                                 v2 = BM_OtherEdgeVert(e, v);
328                                 sub_v3_v3v3(co, v2->co, v->co);
329                                 if (has_elens) {
330                                         float elen = *(float *)CustomData_bmesh_get_n(&bm->edata, e->head.data, CD_PROP_FLT, li);
331
332                                         normalize_v3(co);
333                                         mul_v3_fl(co, elen);
334                                 }
335                                 
336                                 mul_v3_fl(co, fac);
337                                 add_v3_v3(co, v->co);
338                                 
339                                 v2 = BM_Make_Vert(bm, co, v);
340                                 ETAG_SET(e, v, v2);
341                         }
342                 }
343         }
344         
345         for (i = 0; i < BLI_array_count(faces); i++) {
346                 BMLoop *l;
347                 BMIter liter;
348                 
349                 BMO_SetFlag(bm, faces[i], FACE_OLD);
350                 
351                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, faces[i]) {
352                         float co[3];
353
354                         if (BMO_TestFlag(bm, l->e, BEVEL_FLAG)) {
355                                 if (BMO_TestFlag(bm, l->prev->e, BEVEL_FLAG))
356                                 {
357                                         tag = tags + BM_GetIndex(l);
358                                         calc_corner_co(bm, l, fac, co, do_dist, do_even);
359                                         tag->newv = BM_Make_Vert(bm, co, l->v);
360                                 }
361                                 else {
362                                         tag = tags + BM_GetIndex(l);
363                                         tag->newv = ETAG_GET(l->prev->e, l->v);
364                                         
365                                         if (!tag->newv) {
366                                                 sub_v3_v3v3(co, l->prev->v->co, l->v->co);
367                                                 if (has_elens) {
368                                                         float elen = *(float *)CustomData_bmesh_get_n(&bm->edata, l->prev->e->head.data, CD_PROP_FLT, li);
369
370                                                         normalize_v3(co);
371                                                         mul_v3_fl(co, elen);
372                                                 }
373                                                                 
374                                                 mul_v3_fl(co, fac);
375                                                 add_v3_v3(co, l->v->co);
376                                         
377                                                 tag->newv = BM_Make_Vert(bm, co, l->v);
378                                                 
379                                                 ETAG_SET(l->prev->e, l->v, tag->newv);
380                                         }
381                                 }
382                         }
383                         else if (BMO_TestFlag(bm, l->v, BEVEL_FLAG)) {
384                                 tag = tags + BM_GetIndex(l);
385                                 tag->newv = ETAG_GET(l->e, l->v);                               
386                 
387                                 if (!tag->newv) {
388                                         sub_v3_v3v3(co, l->next->v->co, l->v->co);
389                                         if (has_elens) {
390                                                 float elen = *(float *)CustomData_bmesh_get_n(&bm->edata, l->e->head.data, CD_PROP_FLT, li);
391
392                                                 normalize_v3(co);
393                                                 mul_v3_fl(co, elen);
394                                         }
395                                         
396                                         mul_v3_fl(co, fac);
397                                         add_v3_v3(co, l->v->co);
398                         
399                                         tag = tags + BM_GetIndex(l);
400                                         tag->newv = BM_Make_Vert(bm, co, l->v);
401                                         
402                                         ETAG_SET(l->e, l->v, tag->newv);
403                                 }                                       
404                         }
405                         else {
406                                 tag = tags + BM_GetIndex(l);
407                                 tag->newv = l->v;
408                                 BMO_ClearFlag(bm, l->v, BEVEL_DEL);
409                         }
410                 }
411         }
412         
413         /* create new faces inset from original face */
414         for (i = 0; i < BLI_array_count(faces); i++) {
415                 BMLoop *l;
416                 BMIter liter;
417                 BMFace *f;
418                 BMVert *lastv = NULL, *firstv = NULL;
419
420                 BMO_SetFlag(bm, faces[i], BEVEL_DEL);
421                 
422                 BLI_array_empty(verts);
423                 BLI_array_empty(edges);
424                 
425                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, faces[i]) {
426                         BMVert *v2;
427                         
428                         tag = tags + BM_GetIndex(l);
429                         BLI_array_append(verts, tag->newv);
430                         
431                         if (!firstv)
432                                 firstv = tag->newv;
433                         
434                         if (lastv) {
435                                 e = BM_Make_Edge(bm, lastv, tag->newv, l->e, 1);
436                                 BM_Copy_Attributes(bm, bm, l->prev->e, e);
437                                 BLI_array_append(edges, e);
438                         }
439                         lastv = tag->newv;
440                         
441                         v2 = ETAG_GET(l->e, l->next->v);
442                         
443                         tag = tags + BM_GetIndex(l->next);
444                         if (!BMO_TestFlag(bm, l->e, BEVEL_FLAG) && v2 && v2 != tag->newv) {
445                                 BLI_array_append(verts, v2);
446                                 
447                                 e = BM_Make_Edge(bm, lastv, v2, l->e, 1);
448                                 BM_Copy_Attributes(bm, bm, l->e, e);
449                                 
450                                 BLI_array_append(edges, e);
451                                 lastv = v2;
452                         }
453                 }
454                 
455                 e = BM_Make_Edge(bm, firstv, lastv, BM_FACE_FIRST_LOOP(faces[i])->e, 1);
456                 if (BM_FACE_FIRST_LOOP(faces[i])->prev->e != e) 
457                         BM_Copy_Attributes(bm, bm, BM_FACE_FIRST_LOOP(faces[i])->prev->e, e);
458                 BLI_array_append(edges, e);
459                 
460                 f = BM_Make_Ngon(bm, verts[0], verts[1], edges, BLI_array_count(edges), 0);
461                 if (!f) {
462                         printf("%s: could not make face!\n", __func__);
463                         continue;
464                 }
465                         
466                 BMO_SetFlag(bm, f, FACE_NEW);
467         }
468
469         for (i = 0; i < BLI_array_count(faces); i++) {
470                 BMLoop *l;
471                 BMIter liter;
472                 int j;
473                 
474                 /* create quad spans between split edge */
475                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, faces[i]) {
476                         BMVert *v1 = NULL, *v2 = NULL, *v3 = NULL, *v4 = NULL;
477                         
478                         if (!BMO_TestFlag(bm, l->e, BEVEL_FLAG))
479                                 continue;
480                         
481                         v1 = tags[BM_GetIndex(l)].newv;
482                         v2 = tags[BM_GetIndex(l->next)].newv;
483                         if (l->radial_next != l) {
484                                 v3 = tags[BM_GetIndex(l->radial_next)].newv;
485                                 if (l->radial_next->next->v == l->next->v) {
486                                         v4 = v3;
487                                         v3 = tags[BM_GetIndex(l->radial_next->next)].newv;
488                                 }
489                                 else {
490                                         v4 = tags[BM_GetIndex(l->radial_next->next)].newv;
491                                 }
492                         }
493                         else {
494                                 /* the loop is on a boundar */
495                                 v3 = l->next->v;
496                                 v4 = l->v;
497                                 
498                                 for (j = 0; j < 2; j++) {
499                                         BMIter eiter;
500                                         BMVert *v = j ? v4 : v3;
501
502                                         BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
503                                                 if (!BM_Vert_In_Edge(e, v3) || !BM_Vert_In_Edge(e, v4))
504                                                         continue;
505                                                 
506                                                 if (!BMO_TestFlag(bm, e, BEVEL_FLAG) && BMO_TestFlag(bm, e, EDGE_OLD)) {
507                                                         BMVert *vv;
508                                                         
509                                                         vv = ETAG_GET(e, v);
510                                                         if (!vv || BMO_TestFlag(bm, vv, BEVEL_FLAG))
511                                                                 continue;
512                                                         
513                                                         if (j)
514                                                                 v1 = vv;
515                                                         else
516                                                                 v2 = vv;
517                                                         break;
518                                                 }
519                                         }
520                                 }
521
522                                 BMO_ClearFlag(bm, v3, BEVEL_DEL);
523                                 BMO_ClearFlag(bm, v4, BEVEL_DEL);
524                         }
525                         
526                         if (v1 != v2 && v2 != v3 && v3 != v4) {
527                                 BMIter liter2;
528                                 BMLoop *l2, *l3;
529                                 BMEdge *e1, *e2;
530                                 float d1, d2, *d3;
531                                 
532                                 f = BM_Make_Face_QuadTri(bm, v4, v3, v2, v1, l->f, 1);
533
534                                 e1 = BM_Edge_Exist(v4, v3);
535                                 e2 = BM_Edge_Exist(v2, v1);
536                                 BM_Copy_Attributes(bm, bm, l->e, e1);
537                                 BM_Copy_Attributes(bm, bm, l->e, e2);
538                                 
539                                 /* set edge lengths of cross edges as the average of the cross edges they're based o */
540                                 if (has_elens) {
541                                         /* angle happens not to be used. why? - not sure it just isnt - campbell.
542                                          * leave this in incase we need to use it later */
543 #if 0
544                                         float ang;
545 #endif
546                                         e1 = BM_Edge_Exist(v1, v4);
547                                         e2 = BM_Edge_Exist(v2, v3);
548                                         
549                                         if (l->radial_next->v == l->v) {
550                                                 l2 = l->radial_next->prev;
551                                                 l3 = l->radial_next->next;
552                                         }
553                                         else {
554                                                 l2 = l->radial_next->next;
555                                                 l3 = l->radial_next->prev;
556                                         }
557                                         
558                                         d3 = CustomData_bmesh_get_n(&bm->edata, e1->head.data, CD_PROP_FLT, li);
559                                         d1 = *(float *)CustomData_bmesh_get_n(&bm->edata, l->prev->e->head.data, CD_PROP_FLT, li);
560                                         d2 = *(float *)CustomData_bmesh_get_n(&bm->edata, l2->e->head.data, CD_PROP_FLT, li);
561 #if 0
562                                         ang = angle_v3v3v3(l->prev->v->co, l->v->co, BM_OtherEdgeVert(l2->e, l->v)->co);
563 #endif
564                                         *d3 = (d1 + d2) * 0.5f;
565                                         
566                                         d3 = CustomData_bmesh_get_n(&bm->edata, e2->head.data, CD_PROP_FLT, li);
567                                         d1 = *(float *)CustomData_bmesh_get_n(&bm->edata, l->next->e->head.data, CD_PROP_FLT, li);
568                                         d2 = *(float *)CustomData_bmesh_get_n(&bm->edata, l3->e->head.data, CD_PROP_FLT, li);
569 #if 0
570                                         ang = angle_v3v3v3(BM_OtherEdgeVert(l->next->e, l->next->v)->co, l->next->v->co,
571                                                            BM_OtherEdgeVert(l3->e, l->next->v)->co);
572 #endif
573                                         *d3 = (d1 + d2) * 0.5f;
574                                 }
575
576                                 if (!f) {
577                                         fprintf(stderr, "%s: face index out of range! (bmesh internal error)\n", __func__);
578                                         continue;
579                                 }
580                                 
581                                 BMO_SetFlag(bm, f, FACE_NEW|FACE_SPAN);
582                                 
583                                 /* un-tag edges in f for deletio */
584                                 BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_FACE, f) {
585                                         BMO_ClearFlag(bm, l2->e, BEVEL_DEL);
586                                 }
587                         }
588                         else {
589                                 f = NULL;
590                         }
591                 }       
592         }
593         
594         /* fill in holes at vertices */
595         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
596                 BMIter eiter;
597                 BMVert *vv, *vstart = NULL, *lastv = NULL;
598                 SmallHash tmphash;
599                 int rad, insorig = 0, err = 0;
600
601                 BLI_smallhash_init(&tmphash);
602                                 
603                 if (!BMO_TestFlag(bm, v, BEVEL_FLAG))
604                         continue;
605                 
606                 BLI_array_empty(verts);
607                 BLI_array_empty(edges);
608                 
609                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
610                         BMIter liter;
611                         BMVert *v1 = NULL, *v2 = NULL;
612                         BMLoop *l;
613                         
614                         if (BM_Edge_FaceCount(e) < 2)
615                                 insorig = 1;
616                         
617                         if (BM_GetIndex(e) == -1)
618                                 continue;
619                         
620                         rad = 0;
621                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_EDGE, e) {
622                                 if (!BMO_TestFlag(bm, l->f, FACE_OLD))
623                                         continue;
624                                 
625                                 rad++;
626                                 
627                                 tag = tags + BM_GetIndex((l->v == v) ? l : l->next);
628                                 
629                                 if (!v1)
630                                         v1 = tag->newv;
631                                 else if (!v2)
632                                         v2 = tag->newv;
633                         }
634                         
635                         if (rad < 2)
636                                 insorig = 1;
637                         
638                         if (!v1)
639                                 v1 = ETAG_GET(e, v);
640                         if (!v2 || v1 == v2)
641                                 v2 = ETAG_GET(e, v);
642                         
643                         if (v1) {
644                                 if (!BLI_smallhash_haskey(&tmphash, (intptr_t)v1)) {
645                                         BLI_array_append(verts, v1);
646                                         BLI_smallhash_insert(&tmphash, (intptr_t)v1, NULL);
647                                 }
648                                 
649                                 if (v2 && v1 != v2 && !BLI_smallhash_haskey(&tmphash, (intptr_t)v2)) {
650                                         BLI_array_append(verts, v2);
651                                         BLI_smallhash_insert(&tmphash, (intptr_t)v2, NULL);
652                                 }
653                         }
654                 }
655                 
656                 if (!BLI_array_count(verts))
657                         continue;
658                 
659                 if (insorig) {
660                         BLI_array_append(verts, v);
661                         BLI_smallhash_insert(&tmphash, (intptr_t)v, NULL);
662                 }
663                 
664                 /* find edges that exist between vertices in verts.  this is basically
665                  * a topological walk of the edges connecting them */
666                 vstart = vstart ? vstart : verts[0];
667                 vv = vstart;
668                 do {
669                         BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, vv) {
670                                 BMVert *vv2 = BM_OtherEdgeVert(e, vv);
671                                 
672                                 if (vv2 != lastv && BLI_smallhash_haskey(&tmphash, (intptr_t)vv2)) {
673                                         /* if we've go over the same vert twice, break out of outer loop */
674                                         if (BLI_smallhash_lookup(&tmphash, (intptr_t)vv2) != NULL) {
675                                                 e = NULL;
676                                                 err = 1;
677                                                 break;
678                                         }
679                                         
680                                         /* use self pointer as ta */
681                                         BLI_smallhash_remove(&tmphash, (intptr_t)vv2);
682                                         BLI_smallhash_insert(&tmphash, (intptr_t)vv2, vv2);
683                                         
684                                         lastv = vv;
685                                         BLI_array_append(edges, e);
686                                         vv = vv2;
687                                         break;
688                                 }
689                         }
690
691                         if (e == NULL) {
692                                 break;
693                         }
694                 } while (vv != vstart);
695                 
696                 if (err) {
697                         continue;
698                 }
699
700                 /* there may not be a complete loop of edges, so start again and make
701                  * final edge afterwards.  in this case, the previous loop worked to
702                  * find one of the two edges at the extremes. */
703                 if (vv != vstart) {
704                         /* undo previous taggin */
705                         for (i = 0; i < BLI_array_count(verts); i++) {
706                                 BLI_smallhash_remove(&tmphash, (intptr_t)verts[i]);
707                                 BLI_smallhash_insert(&tmphash, (intptr_t)verts[i], NULL);
708                         }
709
710                         vstart = vv;
711                         lastv = NULL;
712                         BLI_array_empty(edges);
713                         do {
714                                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, vv) {
715                                         BMVert *vv2 = BM_OtherEdgeVert(e, vv);
716                                         
717                                         if (vv2 != lastv && BLI_smallhash_haskey(&tmphash, (intptr_t)vv2)) {
718                                                 /* if we've go over the same vert twice, break out of outer loo */
719                                                 if (BLI_smallhash_lookup(&tmphash, (intptr_t)vv2) != NULL) {
720                                                         e = NULL;
721                                                         err = 1;
722                                                         break;
723                                                 }
724                                                 
725                                                 /* use self pointer as ta */
726                                                 BLI_smallhash_remove(&tmphash, (intptr_t)vv2);
727                                                 BLI_smallhash_insert(&tmphash, (intptr_t)vv2, vv2);
728                                                 
729                                                 lastv = vv;
730                                                 BLI_array_append(edges, e);
731                                                 vv = vv2;
732                                                 break;
733                                         }
734                                 }
735                                 if (e == NULL)
736                                         break;
737                         } while (vv != vstart);
738                         
739                         if (!err) {
740                                 e = BM_Make_Edge(bm, vv, vstart, NULL, 1);
741                                 BLI_array_append(edges, e);
742                         }
743                 }
744                 
745                 if (err)
746                         continue;
747                 
748                 if (BLI_array_count(edges) >= 3) {
749                         BMFace *f;
750                         
751                         if (BM_Face_Exists(bm, verts, BLI_array_count(verts), &f))
752                                 continue;
753                         
754                         f = BM_Make_Ngon(bm, lastv, vstart, edges, BLI_array_count(edges), 0);
755                         if (!f) {
756                                 fprintf(stderr, "%s: in bevel vert fill! (bmesh internal error)\n", __func__);
757                         }
758                         else {
759                                 BMO_SetFlag(bm, f, FACE_NEW|FACE_HOLE);
760                         }
761                 }
762                 BLI_smallhash_release(&tmphash);
763         }
764         
765         /* copy over customdat */
766         for (i = 0; i < BLI_array_count(faces); i++) {
767                 BMLoop *l;
768                 BMIter liter;
769                 BMFace *f = faces[i];
770                 
771                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
772                         BMLoop *l2;
773                         BMIter liter2;
774                         
775                         tag = tags + BM_GetIndex(l);
776                         if (!tag->newv)
777                                 continue;
778                         
779                         BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_VERT, tag->newv) {
780                                 if (!BMO_TestFlag(bm, l2->f, FACE_NEW) || (l2->v != tag->newv && l2->v != l->v))
781                                         continue;
782                                 
783                                 if (tag->newv != l->v || HasMDisps) {
784                                         BM_Copy_Attributes(bm, bm, l->f, l2->f);
785                                         BM_loop_interp_from_face(bm, l2, l->f, 1, 1);
786                                 }
787                                 else {
788                                         BM_Copy_Attributes(bm, bm, l->f, l2->f);
789                                         BM_Copy_Attributes(bm, bm, l, l2);
790                                 }
791                                 
792                                 if (HasMDisps) {
793                                         BMLoop *l3;
794                                         BMIter liter3;
795                                         
796                                         BM_ITER(l3, &liter3, bm, BM_LOOPS_OF_FACE, l2->f) {
797                                                 BM_loop_interp_multires(bm, l3, l->f);
798                                         }
799                                 }
800                         }
801                 }
802         }
803         
804         /* handle vertices along boundary edge */
805         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
806                 if (BMO_TestFlag(bm, v, VERT_OLD) && BMO_TestFlag(bm, v, BEVEL_FLAG) && !BMO_TestFlag(bm, v, BEVEL_DEL)) {
807                         BMLoop *l;
808                         BMLoop *lorig = NULL;
809                         BMIter liter;
810                         
811                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, v) {
812                                 // BMIter liter2;
813                                 // BMLoop *l2 = l->v == v ? l : l->next, *l3;
814                                 
815                                 if (BMO_TestFlag(bm, l->f, FACE_OLD)) {
816                                         lorig = l;
817                                         break;
818                                 }
819                         }
820                         
821                         if (!lorig)
822                                 continue;
823                         
824                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, v) {
825                                 BMLoop *l2 = l->v == v ? l : l->next;
826                                 
827                                 BM_Copy_Attributes(bm, bm, lorig->f, l2->f);
828                                 BM_Copy_Attributes(bm, bm, lorig, l2);
829                         }
830                 }
831         }
832 #if 0
833         /* clean up any remaining 2-edged face */
834         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
835                 if (f->len == 2) {
836                         BMFace *faces[2] = {f, BM_FACE_FIRST_LOOP(f)->radial_next->f};
837                         
838                         if (faces[0] == faces[1])
839                                 BM_Kill_Face(bm, f);
840                         else
841                                 BM_Join_Faces(bm, faces, 2);
842                 }
843         }
844 #endif
845         
846         BMO_CallOpf(bm, "del geom=%fv context=%i", BEVEL_DEL, DEL_VERTS);
847
848         /* clean up any edges that might not get properly delete */
849         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
850                 if (BMO_TestFlag(bm, e, EDGE_OLD) && !e->l)
851                         BMO_SetFlag(bm, e, BEVEL_DEL);
852         }
853
854         BMO_CallOpf(bm, "del geom=%fe context=%i", BEVEL_DEL, DEL_EDGES);
855         BMO_CallOpf(bm, "del geom=%ff context=%i", BEVEL_DEL, DEL_FACES);
856         
857         BLI_smallhash_release(&hash);
858         BLI_array_free(tags);
859         BLI_array_free(etags);
860         BLI_array_free(verts);
861         BLI_array_free(edges);
862         BLI_array_free(faces);
863         
864         BMO_Flag_To_Slot(bm, op, "face_spans", FACE_SPAN, BM_FACE);
865         BMO_Flag_To_Slot(bm, op, "face_holes", FACE_HOLE, BM_FACE);
866 }