added boolean type for bmesh operators, will make python wrapping clearer and also...
[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 bmesh_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                                                         else
528                                                                 v2 = vv;
529                                                         break;
530                                                 }
531                                         }
532                                 }
533
534                                 BMO_elem_flag_disable(bm, v3, BEVEL_DEL);
535                                 BMO_elem_flag_disable(bm, v4, BEVEL_DEL);
536                         }
537                         
538                         if (v1 != v2 && v2 != v3 && v3 != v4) {
539                                 BMIter liter2;
540                                 BMLoop *l2, *l3;
541                                 BMEdge *e1, *e2;
542                                 float d1, d2, *d3;
543                                 
544                                 f = BM_face_create_quad_tri(bm, v4, v3, v2, v1, l->f, TRUE);
545
546                                 e1 = BM_edge_exists(v4, v3);
547                                 e2 = BM_edge_exists(v2, v1);
548                                 BM_elem_attrs_copy(bm, bm, l->e, e1);
549                                 BM_elem_attrs_copy(bm, bm, l->e, e2);
550                                 
551                                 /* set edge lengths of cross edges as the average of the cross edges they're based o */
552                                 if (has_elens) {
553                                         /* angle happens not to be used. why? - not sure it just isnt - campbell.
554                                          * leave this in incase we need to use it later */
555 #if 0
556                                         float ang;
557 #endif
558                                         e1 = BM_edge_exists(v1, v4);
559                                         e2 = BM_edge_exists(v2, v3);
560                                         
561                                         if (l->radial_next->v == l->v) {
562                                                 l2 = l->radial_next->prev;
563                                                 l3 = l->radial_next->next;
564                                         }
565                                         else {
566                                                 l2 = l->radial_next->next;
567                                                 l3 = l->radial_next->prev;
568                                         }
569                                         
570                                         d3 = CustomData_bmesh_get_n(&bm->edata, e1->head.data, CD_PROP_FLT, li);
571                                         d1 = *(float *)CustomData_bmesh_get_n(&bm->edata, l->prev->e->head.data, CD_PROP_FLT, li);
572                                         d2 = *(float *)CustomData_bmesh_get_n(&bm->edata, l2->e->head.data, CD_PROP_FLT, li);
573 #if 0
574                                         ang = angle_v3v3v3(l->prev->v->co, l->v->co, BM_edge_other_vert(l2->e, l->v)->co);
575 #endif
576                                         *d3 = (d1 + d2) * 0.5f;
577                                         
578                                         d3 = CustomData_bmesh_get_n(&bm->edata, e2->head.data, CD_PROP_FLT, li);
579                                         d1 = *(float *)CustomData_bmesh_get_n(&bm->edata, l->next->e->head.data, CD_PROP_FLT, li);
580                                         d2 = *(float *)CustomData_bmesh_get_n(&bm->edata, l3->e->head.data, CD_PROP_FLT, li);
581 #if 0
582                                         ang = angle_v3v3v3(BM_edge_other_vert(l->next->e, l->next->v)->co, l->next->v->co,
583                                                            BM_edge_other_vert(l3->e, l->next->v)->co);
584 #endif
585                                         *d3 = (d1 + d2) * 0.5f;
586                                 }
587
588                                 if (!f) {
589                                         fprintf(stderr, "%s: face index out of range! (bmesh internal error)\n", __func__);
590                                         continue;
591                                 }
592                                 
593                                 BMO_elem_flag_enable(bm, f, FACE_NEW|FACE_SPAN);
594                                 
595                                 /* un-tag edges in f for deletio */
596                                 BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_FACE, f) {
597                                         BMO_elem_flag_disable(bm, l2->e, BEVEL_DEL);
598                                 }
599                         }
600                         else {
601                                 f = NULL;
602                         }
603                 }
604         }
605         
606         /* fill in holes at vertices */
607         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
608                 BMIter eiter;
609                 BMVert *vv, *vstart = NULL, *lastv = NULL;
610                 SmallHash tmphash;
611                 int rad, insorig = 0, err = 0;
612
613                 BLI_smallhash_init(&tmphash);
614
615                 if (!BMO_elem_flag_test(bm, v, BEVEL_FLAG))
616                         continue;
617                 
618                 BLI_array_empty(verts);
619                 BLI_array_empty(edges);
620                 
621                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
622                         BMIter liter;
623                         BMVert *v1 = NULL, *v2 = NULL;
624                         BMLoop *l;
625                         
626                         if (BM_edge_face_count(e) < 2)
627                                 insorig = 1;
628                         
629                         if (BM_elem_index_get(e) == -1)
630                                 continue;
631                         
632                         rad = 0;
633                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_EDGE, e) {
634                                 if (!BMO_elem_flag_test(bm, l->f, FACE_OLD))
635                                         continue;
636                                 
637                                 rad++;
638                                 
639                                 tag = tags + BM_elem_index_get((l->v == v) ? l : l->next);
640                                 
641                                 if (!v1)
642                                         v1 = tag->newv;
643                                 else if (!v2)
644                                         v2 = tag->newv;
645                         }
646                         
647                         if (rad < 2)
648                                 insorig = 1;
649                         
650                         if (!v1)
651                                 v1 = ETAG_GET(e, v);
652                         if (!v2 || v1 == v2)
653                                 v2 = ETAG_GET(e, v);
654                         
655                         if (v1) {
656                                 if (!BLI_smallhash_haskey(&tmphash, (intptr_t)v1)) {
657                                         BLI_array_append(verts, v1);
658                                         BLI_smallhash_insert(&tmphash, (intptr_t)v1, NULL);
659                                 }
660                                 
661                                 if (v2 && v1 != v2 && !BLI_smallhash_haskey(&tmphash, (intptr_t)v2)) {
662                                         BLI_array_append(verts, v2);
663                                         BLI_smallhash_insert(&tmphash, (intptr_t)v2, NULL);
664                                 }
665                         }
666                 }
667                 
668                 if (!BLI_array_count(verts))
669                         continue;
670                 
671                 if (insorig) {
672                         BLI_array_append(verts, v);
673                         BLI_smallhash_insert(&tmphash, (intptr_t)v, NULL);
674                 }
675                 
676                 /* find edges that exist between vertices in verts.  this is basically
677                  * a topological walk of the edges connecting them */
678                 vstart = vstart ? vstart : verts[0];
679                 vv = vstart;
680                 do {
681                         BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, vv) {
682                                 BMVert *vv2 = BM_edge_other_vert(e, vv);
683                                 
684                                 if (vv2 != lastv && BLI_smallhash_haskey(&tmphash, (intptr_t)vv2)) {
685                                         /* if we've go over the same vert twice, break out of outer loop */
686                                         if (BLI_smallhash_lookup(&tmphash, (intptr_t)vv2) != NULL) {
687                                                 e = NULL;
688                                                 err = 1;
689                                                 break;
690                                         }
691                                         
692                                         /* use self pointer as ta */
693                                         BLI_smallhash_remove(&tmphash, (intptr_t)vv2);
694                                         BLI_smallhash_insert(&tmphash, (intptr_t)vv2, vv2);
695                                         
696                                         lastv = vv;
697                                         BLI_array_append(edges, e);
698                                         vv = vv2;
699                                         break;
700                                 }
701                         }
702
703                         if (e == NULL) {
704                                 break;
705                         }
706                 } while (vv != vstart);
707                 
708                 if (err) {
709                         continue;
710                 }
711
712                 /* there may not be a complete loop of edges, so start again and make
713                  * final edge afterwards.  in this case, the previous loop worked to
714                  * find one of the two edges at the extremes. */
715                 if (vv != vstart) {
716                         /* undo previous taggin */
717                         for (i = 0; i < BLI_array_count(verts); i++) {
718                                 BLI_smallhash_remove(&tmphash, (intptr_t)verts[i]);
719                                 BLI_smallhash_insert(&tmphash, (intptr_t)verts[i], NULL);
720                         }
721
722                         vstart = vv;
723                         lastv = NULL;
724                         BLI_array_empty(edges);
725                         do {
726                                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, vv) {
727                                         BMVert *vv2 = BM_edge_other_vert(e, vv);
728                                         
729                                         if (vv2 != lastv && BLI_smallhash_haskey(&tmphash, (intptr_t)vv2)) {
730                                                 /* if we've go over the same vert twice, break out of outer loo */
731                                                 if (BLI_smallhash_lookup(&tmphash, (intptr_t)vv2) != NULL) {
732                                                         e = NULL;
733                                                         err = 1;
734                                                         break;
735                                                 }
736                                                 
737                                                 /* use self pointer as ta */
738                                                 BLI_smallhash_remove(&tmphash, (intptr_t)vv2);
739                                                 BLI_smallhash_insert(&tmphash, (intptr_t)vv2, vv2);
740                                                 
741                                                 lastv = vv;
742                                                 BLI_array_append(edges, e);
743                                                 vv = vv2;
744                                                 break;
745                                         }
746                                 }
747                                 if (e == NULL)
748                                         break;
749                         } while (vv != vstart);
750                         
751                         if (!err) {
752                                 e = BM_edge_create(bm, vv, vstart, NULL, TRUE);
753                                 BLI_array_append(edges, e);
754                         }
755                 }
756                 
757                 if (err)
758                         continue;
759                 
760                 if (BLI_array_count(edges) >= 3) {
761                         BMFace *f;
762                         
763                         if (BM_face_exists(bm, verts, BLI_array_count(verts), &f))
764                                 continue;
765                         
766                         f = BM_face_create_ngon(bm, lastv, vstart, edges, BLI_array_count(edges), FALSE);
767                         if (!f) {
768                                 fprintf(stderr, "%s: in bevel vert fill! (bmesh internal error)\n", __func__);
769                         }
770                         else {
771                                 BMO_elem_flag_enable(bm, f, FACE_NEW|FACE_HOLE);
772                         }
773                 }
774                 BLI_smallhash_release(&tmphash);
775         }
776         
777         /* copy over customdat */
778         for (i = 0; i < BLI_array_count(faces); i++) {
779                 BMLoop *l;
780                 BMIter liter;
781                 BMFace *f = faces[i];
782                 
783                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
784                         BMLoop *l2;
785                         BMIter liter2;
786                         
787                         tag = tags + BM_elem_index_get(l);
788                         if (!tag->newv)
789                                 continue;
790                         
791                         BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_VERT, tag->newv) {
792                                 if (!BMO_elem_flag_test(bm, l2->f, FACE_NEW) || (l2->v != tag->newv && l2->v != l->v))
793                                         continue;
794                                 
795                                 if (tag->newv != l->v || HasMDisps) {
796                                         BM_elem_attrs_copy(bm, bm, l->f, l2->f);
797                                         BM_loop_interp_from_face(bm, l2, l->f, TRUE, TRUE);
798                                 }
799                                 else {
800                                         BM_elem_attrs_copy(bm, bm, l->f, l2->f);
801                                         BM_elem_attrs_copy(bm, bm, l, l2);
802                                 }
803                                 
804                                 if (HasMDisps) {
805                                         BMLoop *l3;
806                                         BMIter liter3;
807                                         
808                                         BM_ITER(l3, &liter3, bm, BM_LOOPS_OF_FACE, l2->f) {
809                                                 BM_loop_interp_multires(bm, l3, l->f);
810                                         }
811                                 }
812                         }
813                 }
814         }
815         
816         /* handle vertices along boundary edge */
817         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
818                 if (BMO_elem_flag_test(bm, v, VERT_OLD) &&
819                     BMO_elem_flag_test(bm, v, BEVEL_FLAG) &&
820                     !BMO_elem_flag_test(bm, v, BEVEL_DEL))
821                 {
822                         BMLoop *l;
823                         BMLoop *lorig = NULL;
824                         BMIter liter;
825                         
826                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, v) {
827                                 // BMIter liter2;
828                                 // BMLoop *l2 = l->v == v ? l : l->next, *l3;
829                                 
830                                 if (BMO_elem_flag_test(bm, l->f, FACE_OLD)) {
831                                         lorig = l;
832                                         break;
833                                 }
834                         }
835                         
836                         if (!lorig)
837                                 continue;
838                         
839                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, v) {
840                                 BMLoop *l2 = l->v == v ? l : l->next;
841                                 
842                                 BM_elem_attrs_copy(bm, bm, lorig->f, l2->f);
843                                 BM_elem_attrs_copy(bm, bm, lorig, l2);
844                         }
845                 }
846         }
847 #if 0
848         /* clean up any remaining 2-edged face */
849         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
850                 if (f->len == 2) {
851                         BMFace *faces[2] = {f, BM_FACE_FIRST_LOOP(f)->radial_next->f};
852                         
853                         if (faces[0] == faces[1])
854                                 BM_face_kill(bm, f);
855                         else
856                                 BM_faces_join(bm, faces, 2);
857                 }
858         }
859 #endif
860
861         BMO_op_callf(bm, "del geom=%fv context=%i", BEVEL_DEL, DEL_VERTS);
862
863         /* clean up any edges that might not get properly delete */
864         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
865                 if (BMO_elem_flag_test(bm, e, EDGE_OLD) && !e->l)
866                         BMO_elem_flag_enable(bm, e, BEVEL_DEL);
867         }
868
869         BMO_op_callf(bm, "del geom=%fe context=%i", BEVEL_DEL, DEL_EDGES);
870         BMO_op_callf(bm, "del geom=%ff context=%i", BEVEL_DEL, DEL_FACES);
871         
872         BLI_smallhash_release(&hash);
873         BLI_array_free(tags);
874         BLI_array_free(etags);
875         BLI_array_free(verts);
876         BLI_array_free(edges);
877         BLI_array_free(faces);
878         
879         BMO_slot_from_flag(bm, op, "face_spans", FACE_SPAN, BM_FACE);
880         BMO_slot_from_flag(bm, op, "face_holes", FACE_HOLE, BM_FACE);
881 }