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