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