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