style cleanup, brackets in else/if, some indentation.
[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                                         tag = tags + BM_elem_index_get(l);
367                                         calc_corner_co(bm, l, fac, co, do_dist, do_even);
368                                         tag->newv = BM_vert_create(bm, co, l->v);
369                                 }
370                                 else {
371                                         tag = tags + BM_elem_index_get(l);
372                                         tag->newv = ETAG_GET(l->prev->e, l->v);
373                                         
374                                         if (!tag->newv) {
375                                                 sub_v3_v3v3(co, l->prev->v->co, l->v->co);
376                                                 if (has_elens) {
377                                                         float elen = *(float *)CustomData_bmesh_get_n(&bm->edata, l->prev->e->head.data,
378                                                                                                       CD_PROP_FLT, li);
379
380                                                         normalize_v3(co);
381                                                         mul_v3_fl(co, elen);
382                                                 }
383
384                                                 mul_v3_fl(co, fac);
385                                                 add_v3_v3(co, l->v->co);
386
387                                                 tag->newv = BM_vert_create(bm, co, l->v);
388                                                 
389                                                 ETAG_SET(l->prev->e, l->v, tag->newv);
390                                         }
391                                 }
392                         }
393                         else if (BMO_elem_flag_test(bm, l->v, BEVEL_FLAG)) {
394                                 tag = tags + BM_elem_index_get(l);
395                                 tag->newv = ETAG_GET(l->e, l->v);
396
397                                 if (!tag->newv) {
398                                         sub_v3_v3v3(co, l->next->v->co, l->v->co);
399                                         if (has_elens) {
400                                                 float elen = *(float *)CustomData_bmesh_get_n(&bm->edata, l->e->head.data, CD_PROP_FLT, li);
401
402                                                 normalize_v3(co);
403                                                 mul_v3_fl(co, elen);
404                                         }
405                                         
406                                         mul_v3_fl(co, fac);
407                                         add_v3_v3(co, l->v->co);
408
409                                         tag = tags + BM_elem_index_get(l);
410                                         tag->newv = BM_vert_create(bm, co, l->v);
411                                         
412                                         ETAG_SET(l->e, l->v, tag->newv);
413                                 }
414                         }
415                         else {
416                                 tag = tags + BM_elem_index_get(l);
417                                 tag->newv = l->v;
418                                 BMO_elem_flag_disable(bm, l->v, BEVEL_DEL);
419                         }
420                 }
421         }
422         
423         /* create new faces inset from original face */
424         for (i = 0; i < BLI_array_count(faces); i++) {
425                 BMLoop *l;
426                 BMIter liter;
427                 BMFace *f;
428                 BMVert *lastv = NULL, *firstv = NULL;
429
430                 BMO_elem_flag_enable(bm, faces[i], BEVEL_DEL);
431                 
432                 BLI_array_empty(verts);
433                 BLI_array_empty(edges);
434                 
435                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, faces[i]) {
436                         BMVert *v2;
437                         
438                         tag = tags + BM_elem_index_get(l);
439                         BLI_array_append(verts, tag->newv);
440                         
441                         if (!firstv)
442                                 firstv = tag->newv;
443                         
444                         if (lastv) {
445                                 e = BM_edge_create(bm, lastv, tag->newv, l->e, TRUE);
446                                 BM_elem_attrs_copy(bm, bm, l->prev->e, e);
447                                 BLI_array_append(edges, e);
448                         }
449                         lastv = tag->newv;
450                         
451                         v2 = ETAG_GET(l->e, l->next->v);
452                         
453                         tag = &tags[BM_elem_index_get(l->next)];
454                         if (!BMO_elem_flag_test(bm, l->e, BEVEL_FLAG) && v2 && v2 != tag->newv) {
455                                 BLI_array_append(verts, v2);
456                                 
457                                 e = BM_edge_create(bm, lastv, v2, l->e, TRUE);
458                                 BM_elem_attrs_copy(bm, bm, l->e, e);
459                                 
460                                 BLI_array_append(edges, e);
461                                 lastv = v2;
462                         }
463                 }
464                 
465                 e = BM_edge_create(bm, firstv, lastv, BM_FACE_FIRST_LOOP(faces[i])->e, TRUE);
466                 if (BM_FACE_FIRST_LOOP(faces[i])->prev->e != e) {
467                         BM_elem_attrs_copy(bm, bm, BM_FACE_FIRST_LOOP(faces[i])->prev->e, e);
468                 }
469                 BLI_array_append(edges, e);
470                 
471                 f = BM_face_create_ngon(bm, verts[0], verts[1], edges, BLI_array_count(edges), FALSE);
472                 if (!f) {
473                         printf("%s: could not make face!\n", __func__);
474                         continue;
475                 }
476
477                 BMO_elem_flag_enable(bm, f, FACE_NEW);
478         }
479
480         for (i = 0; i < BLI_array_count(faces); i++) {
481                 BMLoop *l;
482                 BMIter liter;
483                 int j;
484                 
485                 /* create quad spans between split edge */
486                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, faces[i]) {
487                         BMVert *v1 = NULL, *v2 = NULL, *v3 = NULL, *v4 = NULL;
488                         
489                         if (!BMO_elem_flag_test(bm, l->e, BEVEL_FLAG))
490                                 continue;
491                         
492                         v1 = tags[BM_elem_index_get(l)].newv;
493                         v2 = tags[BM_elem_index_get(l->next)].newv;
494                         if (l->radial_next != l) {
495                                 v3 = tags[BM_elem_index_get(l->radial_next)].newv;
496                                 if (l->radial_next->next->v == l->next->v) {
497                                         v4 = v3;
498                                         v3 = tags[BM_elem_index_get(l->radial_next->next)].newv;
499                                 }
500                                 else {
501                                         v4 = tags[BM_elem_index_get(l->radial_next->next)].newv;
502                                 }
503                         }
504                         else {
505                                 /* the loop is on a boundar */
506                                 v3 = l->next->v;
507                                 v4 = l->v;
508                                 
509                                 for (j = 0; j < 2; j++) {
510                                         BMIter eiter;
511                                         BMVert *v = j ? v4 : v3;
512
513                                         BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
514                                                 if (!BM_vert_in_edge(e, v3) || !BM_vert_in_edge(e, v4))
515                                                         continue;
516                                                 
517                                                 if (!BMO_elem_flag_test(bm, e, BEVEL_FLAG) && BMO_elem_flag_test(bm, e, EDGE_OLD)) {
518                                                         BMVert *vv;
519                                                         
520                                                         vv = ETAG_GET(e, v);
521                                                         if (!vv || BMO_elem_flag_test(bm, vv, BEVEL_FLAG))
522                                                                 continue;
523                                                         
524                                                         if (j) {
525                                                                 v1 = vv;
526                                                         }
527                                                         else {
528                                                                 v2 = vv;
529                                                         }
530                                                         break;
531                                                 }
532                                         }
533                                 }
534
535                                 BMO_elem_flag_disable(bm, v3, BEVEL_DEL);
536                                 BMO_elem_flag_disable(bm, v4, BEVEL_DEL);
537                         }
538                         
539                         if (v1 != v2 && v2 != v3 && v3 != v4) {
540                                 BMIter liter2;
541                                 BMLoop *l2, *l3;
542                                 BMEdge *e1, *e2;
543                                 float d1, d2, *d3;
544                                 
545                                 f = BM_face_create_quad_tri(bm, v4, v3, v2, v1, l->f, TRUE);
546
547                                 e1 = BM_edge_exists(v4, v3);
548                                 e2 = BM_edge_exists(v2, v1);
549                                 BM_elem_attrs_copy(bm, bm, l->e, e1);
550                                 BM_elem_attrs_copy(bm, bm, l->e, e2);
551                                 
552                                 /* set edge lengths of cross edges as the average of the cross edges they're based o */
553                                 if (has_elens) {
554                                         /* angle happens not to be used. why? - not sure it just isnt - campbell.
555                                          * leave this in incase we need to use it later */
556 #if 0
557                                         float ang;
558 #endif
559                                         e1 = BM_edge_exists(v1, v4);
560                                         e2 = BM_edge_exists(v2, v3);
561                                         
562                                         if (l->radial_next->v == l->v) {
563                                                 l2 = l->radial_next->prev;
564                                                 l3 = l->radial_next->next;
565                                         }
566                                         else {
567                                                 l2 = l->radial_next->next;
568                                                 l3 = l->radial_next->prev;
569                                         }
570                                         
571                                         d3 = CustomData_bmesh_get_n(&bm->edata, e1->head.data, CD_PROP_FLT, li);
572                                         d1 = *(float *)CustomData_bmesh_get_n(&bm->edata, l->prev->e->head.data, CD_PROP_FLT, li);
573                                         d2 = *(float *)CustomData_bmesh_get_n(&bm->edata, l2->e->head.data, CD_PROP_FLT, li);
574 #if 0
575                                         ang = angle_v3v3v3(l->prev->v->co, l->v->co, BM_edge_other_vert(l2->e, l->v)->co);
576 #endif
577                                         *d3 = (d1 + d2) * 0.5f;
578                                         
579                                         d3 = CustomData_bmesh_get_n(&bm->edata, e2->head.data, CD_PROP_FLT, li);
580                                         d1 = *(float *)CustomData_bmesh_get_n(&bm->edata, l->next->e->head.data, CD_PROP_FLT, li);
581                                         d2 = *(float *)CustomData_bmesh_get_n(&bm->edata, l3->e->head.data, CD_PROP_FLT, li);
582 #if 0
583                                         ang = angle_v3v3v3(BM_edge_other_vert(l->next->e, l->next->v)->co, l->next->v->co,
584                                                            BM_edge_other_vert(l3->e, l->next->v)->co);
585 #endif
586                                         *d3 = (d1 + d2) * 0.5f;
587                                 }
588
589                                 if (!f) {
590                                         fprintf(stderr, "%s: face index out of range! (bmesh internal error)\n", __func__);
591                                         continue;
592                                 }
593                                 
594                                 BMO_elem_flag_enable(bm, f, FACE_NEW|FACE_SPAN);
595                                 
596                                 /* un-tag edges in f for deletio */
597                                 BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_FACE, f) {
598                                         BMO_elem_flag_disable(bm, l2->e, BEVEL_DEL);
599                                 }
600                         }
601                         else {
602                                 f = NULL;
603                         }
604                 }
605         }
606         
607         /* fill in holes at vertices */
608         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
609                 BMIter eiter;
610                 BMVert *vv, *vstart = NULL, *lastv = NULL;
611                 SmallHash tmphash;
612                 int rad, insorig = 0, err = 0;
613
614                 BLI_smallhash_init(&tmphash);
615
616                 if (!BMO_elem_flag_test(bm, v, BEVEL_FLAG))
617                         continue;
618                 
619                 BLI_array_empty(verts);
620                 BLI_array_empty(edges);
621                 
622                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
623                         BMIter liter;
624                         BMVert *v1 = NULL, *v2 = NULL;
625                         BMLoop *l;
626                         
627                         if (BM_edge_face_count(e) < 2)
628                                 insorig = 1;
629                         
630                         if (BM_elem_index_get(e) == -1)
631                                 continue;
632                         
633                         rad = 0;
634                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_EDGE, e) {
635                                 if (!BMO_elem_flag_test(bm, l->f, FACE_OLD))
636                                         continue;
637                                 
638                                 rad++;
639                                 
640                                 tag = tags + BM_elem_index_get((l->v == v) ? l : l->next);
641                                 
642                                 if (!v1)
643                                         v1 = tag->newv;
644                                 else if (!v2)
645                                         v2 = tag->newv;
646                         }
647                         
648                         if (rad < 2)
649                                 insorig = 1;
650                         
651                         if (!v1)
652                                 v1 = ETAG_GET(e, v);
653                         if (!v2 || v1 == v2)
654                                 v2 = ETAG_GET(e, v);
655                         
656                         if (v1) {
657                                 if (!BLI_smallhash_haskey(&tmphash, (intptr_t)v1)) {
658                                         BLI_array_append(verts, v1);
659                                         BLI_smallhash_insert(&tmphash, (intptr_t)v1, NULL);
660                                 }
661                                 
662                                 if (v2 && v1 != v2 && !BLI_smallhash_haskey(&tmphash, (intptr_t)v2)) {
663                                         BLI_array_append(verts, v2);
664                                         BLI_smallhash_insert(&tmphash, (intptr_t)v2, NULL);
665                                 }
666                         }
667                 }
668                 
669                 if (!BLI_array_count(verts))
670                         continue;
671                 
672                 if (insorig) {
673                         BLI_array_append(verts, v);
674                         BLI_smallhash_insert(&tmphash, (intptr_t)v, NULL);
675                 }
676                 
677                 /* find edges that exist between vertices in verts.  this is basically
678                  * a topological walk of the edges connecting them */
679                 vstart = vstart ? vstart : verts[0];
680                 vv = vstart;
681                 do {
682                         BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, vv) {
683                                 BMVert *vv2 = BM_edge_other_vert(e, vv);
684                                 
685                                 if (vv2 != lastv && BLI_smallhash_haskey(&tmphash, (intptr_t)vv2)) {
686                                         /* if we've go over the same vert twice, break out of outer loop */
687                                         if (BLI_smallhash_lookup(&tmphash, (intptr_t)vv2) != NULL) {
688                                                 e = NULL;
689                                                 err = 1;
690                                                 break;
691                                         }
692                                         
693                                         /* use self pointer as ta */
694                                         BLI_smallhash_remove(&tmphash, (intptr_t)vv2);
695                                         BLI_smallhash_insert(&tmphash, (intptr_t)vv2, vv2);
696                                         
697                                         lastv = vv;
698                                         BLI_array_append(edges, e);
699                                         vv = vv2;
700                                         break;
701                                 }
702                         }
703
704                         if (e == NULL) {
705                                 break;
706                         }
707                 } while (vv != vstart);
708                 
709                 if (err) {
710                         continue;
711                 }
712
713                 /* there may not be a complete loop of edges, so start again and make
714                  * final edge afterwards.  in this case, the previous loop worked to
715                  * find one of the two edges at the extremes. */
716                 if (vv != vstart) {
717                         /* undo previous taggin */
718                         for (i = 0; i < BLI_array_count(verts); i++) {
719                                 BLI_smallhash_remove(&tmphash, (intptr_t)verts[i]);
720                                 BLI_smallhash_insert(&tmphash, (intptr_t)verts[i], NULL);
721                         }
722
723                         vstart = vv;
724                         lastv = NULL;
725                         BLI_array_empty(edges);
726                         do {
727                                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, vv) {
728                                         BMVert *vv2 = BM_edge_other_vert(e, vv);
729                                         
730                                         if (vv2 != lastv && BLI_smallhash_haskey(&tmphash, (intptr_t)vv2)) {
731                                                 /* if we've go over the same vert twice, break out of outer loo */
732                                                 if (BLI_smallhash_lookup(&tmphash, (intptr_t)vv2) != NULL) {
733                                                         e = NULL;
734                                                         err = 1;
735                                                         break;
736                                                 }
737                                                 
738                                                 /* use self pointer as ta */
739                                                 BLI_smallhash_remove(&tmphash, (intptr_t)vv2);
740                                                 BLI_smallhash_insert(&tmphash, (intptr_t)vv2, vv2);
741                                                 
742                                                 lastv = vv;
743                                                 BLI_array_append(edges, e);
744                                                 vv = vv2;
745                                                 break;
746                                         }
747                                 }
748                                 if (e == NULL)
749                                         break;
750                         } while (vv != vstart);
751                         
752                         if (!err) {
753                                 e = BM_edge_create(bm, vv, vstart, NULL, TRUE);
754                                 BLI_array_append(edges, e);
755                         }
756                 }
757                 
758                 if (err)
759                         continue;
760                 
761                 if (BLI_array_count(edges) >= 3) {
762                         BMFace *f;
763                         
764                         if (BM_face_exists(bm, verts, BLI_array_count(verts), &f))
765                                 continue;
766                         
767                         f = BM_face_create_ngon(bm, lastv, vstart, edges, BLI_array_count(edges), FALSE);
768                         if (!f) {
769                                 fprintf(stderr, "%s: in bevel vert fill! (bmesh internal error)\n", __func__);
770                         }
771                         else {
772                                 BMO_elem_flag_enable(bm, f, FACE_NEW|FACE_HOLE);
773                         }
774                 }
775                 BLI_smallhash_release(&tmphash);
776         }
777         
778         /* copy over customdat */
779         for (i = 0; i < BLI_array_count(faces); i++) {
780                 BMLoop *l;
781                 BMIter liter;
782                 BMFace *f = faces[i];
783                 
784                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
785                         BMLoop *l2;
786                         BMIter liter2;
787                         
788                         tag = tags + BM_elem_index_get(l);
789                         if (!tag->newv)
790                                 continue;
791                         
792                         BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_VERT, tag->newv) {
793                                 if (!BMO_elem_flag_test(bm, l2->f, FACE_NEW) || (l2->v != tag->newv && l2->v != l->v))
794                                         continue;
795                                 
796                                 if (tag->newv != l->v || HasMDisps) {
797                                         BM_elem_attrs_copy(bm, bm, l->f, l2->f);
798                                         BM_loop_interp_from_face(bm, l2, l->f, TRUE, TRUE);
799                                 }
800                                 else {
801                                         BM_elem_attrs_copy(bm, bm, l->f, l2->f);
802                                         BM_elem_attrs_copy(bm, bm, l, l2);
803                                 }
804                                 
805                                 if (HasMDisps) {
806                                         BMLoop *l3;
807                                         BMIter liter3;
808                                         
809                                         BM_ITER(l3, &liter3, bm, BM_LOOPS_OF_FACE, l2->f) {
810                                                 BM_loop_interp_multires(bm, l3, l->f);
811                                         }
812                                 }
813                         }
814                 }
815         }
816         
817         /* handle vertices along boundary edge */
818         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
819                 if (BMO_elem_flag_test(bm, v, VERT_OLD) &&
820                     BMO_elem_flag_test(bm, v, BEVEL_FLAG) &&
821                     !BMO_elem_flag_test(bm, v, BEVEL_DEL))
822                 {
823                         BMLoop *l;
824                         BMLoop *lorig = NULL;
825                         BMIter liter;
826                         
827                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, v) {
828                                 // BMIter liter2;
829                                 // BMLoop *l2 = l->v == v ? l : l->next, *l3;
830                                 
831                                 if (BMO_elem_flag_test(bm, l->f, FACE_OLD)) {
832                                         lorig = l;
833                                         break;
834                                 }
835                         }
836                         
837                         if (!lorig)
838                                 continue;
839                         
840                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, v) {
841                                 BMLoop *l2 = l->v == v ? l : l->next;
842                                 
843                                 BM_elem_attrs_copy(bm, bm, lorig->f, l2->f);
844                                 BM_elem_attrs_copy(bm, bm, lorig, l2);
845                         }
846                 }
847         }
848 #if 0
849         /* clean up any remaining 2-edged face */
850         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
851                 if (f->len == 2) {
852                         BMFace *faces[2] = {f, BM_FACE_FIRST_LOOP(f)->radial_next->f};
853                         
854                         if (faces[0] == faces[1])
855                                 BM_face_kill(bm, f);
856                         else
857                                 BM_faces_join(bm, faces, 2);
858                 }
859         }
860 #endif
861
862         BMO_op_callf(bm, "del geom=%fv context=%i", BEVEL_DEL, DEL_VERTS);
863
864         /* clean up any edges that might not get properly delete */
865         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
866                 if (BMO_elem_flag_test(bm, e, EDGE_OLD) && !e->l)
867                         BMO_elem_flag_enable(bm, e, BEVEL_DEL);
868         }
869
870         BMO_op_callf(bm, "del geom=%fe context=%i", BEVEL_DEL, DEL_EDGES);
871         BMO_op_callf(bm, "del geom=%ff context=%i", BEVEL_DEL, DEL_FACES);
872         
873         BLI_smallhash_release(&hash);
874         BLI_array_free(tags);
875         BLI_array_free(etags);
876         BLI_array_free(verts);
877         BLI_array_free(edges);
878         BLI_array_free(faces);
879         
880         BMO_slot_buffer_from_flag(bm, op, "face_spans", FACE_SPAN, BM_FACE);
881         BMO_slot_buffer_from_flag(bm, op, "face_holes", FACE_HOLE, BM_FACE);
882 }