e18920fc98efc27902e459585bdfdcd8c22f74ec
[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, Aleksandr Mokhov, Howard Trickey
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/bmesh/operators/bmo_bevel.c
24  *  \ingroup bmesh
25  */
26
27 #include "MEM_guardedalloc.h"
28
29 #include "BLI_listbase.h"
30 #include "BLI_array.h"
31 #include "BLI_math.h"
32 #include "BLI_smallhash.h"
33
34 #include "BKE_customdata.h"
35
36 #include "bmesh.h"
37
38 #include "intern/bmesh_operators_private.h" /* own include */
39
40 #define NEW_BEVEL 1
41
42 #ifdef NEW_BEVEL
43 #define BEVEL_FLAG      1
44 #define EDGE_SELECTED   2
45
46 #define BEVEL_EPSILON  1e-6
47
48 /* Constructed vertex, sometimes later instantiated as BMVert */
49 typedef struct NewVert {
50         float co[3];
51         BMVert *v;
52 } NewVert;
53
54 struct BoundVert;
55
56 /* Data for one end of an edge involved in a bevel */
57 typedef struct EdgeHalf {
58         struct EdgeHalf *next, *prev;   /* in CCW order */
59         BMEdge *e;                  /* original mesh edge */
60         int isbev;                  /* is this edge beveled? */
61         int isrev;                  /* is e->v2 the vertex at this end? */
62         int seg;                    /* how many segments for the bevel */
63         float offset;               /* offset for this edge */
64         BMFace *fprev;              /* face between this edge and previous, if any */
65         BMFace *fnext;              /* face between this edge and next, if any */
66         struct BoundVert *leftv;    /* left boundary vert (looking along edge to end) */
67         struct BoundVert *rightv;   /* right boundary vert, if beveled */
68 } EdgeHalf;
69
70 /* An element in a cyclic boundary of a Vertex Mesh (VMesh) */
71 typedef struct BoundVert {
72         struct BoundVert *next, *prev;  /* in CCW order */
73         int index;          /* used for vmesh indexing */
74         NewVert nv;
75         EdgeHalf *efirst;   /* first of edges attached here: in CCW order */
76         EdgeHalf *elast;
77         EdgeHalf *ebev;     /* beveled edge whose left side is attached here, if any */
78 } BoundVert;
79
80 /* Mesh structure replacing a vertex */
81 typedef struct VMesh {
82         enum {
83                 M_NONE,         /* no polygon mesh needed */
84                 M_POLY,         /* a simple polygon */
85                 M_ADJ,          /* "adjacent edges" mesh pattern */
86                 M_CROSS,        /* "cross edges" mesh pattern */
87         } mesh_kind;
88         int count;          /* number of vertices in the boundary */
89         int seg;            /* common # of segments for segmented edges */
90         BoundVert *boundstart;      /* start of boundary double-linked list */
91         NewVert *mesh;          /* allocated array - size and structure depends on kind */
92 } VMesh;
93
94 /* Data for a vertex involved in a bevel */
95 typedef struct BevVert {
96         struct BevVert *next, *prev;
97         BMVert *v;          /* original mesh vertex */
98         int edgecount;          /* total number of edges around the vertex */
99         int selcount;           /* number of selected edges around the vertex */
100         EdgeHalf *edges;        /* array of size edgecount; CCW order from vertex normal side */
101         VMesh *vmesh;           /* mesh structure for replacing vertex */
102 } BevVert;
103
104 /*
105  * Bevel parameters and state
106  */
107 typedef struct BevelParams {
108         ListBase vertList;      /* list of BevVert for each vertex involved in bevel */
109         float offset;           /* blender units to offset each side of a beveled edge */
110         int seg;                /* number of segments in beveled edge profile */
111
112         BMOperator *op;
113 } BevelParams;
114
115 /* Make a new BoundVert of the given kind, insert it at the end of the circular linked
116  * list with entry point bv->boundstart, and return it. */
117 static BoundVert *add_new_bound_vert(VMesh *vm, float co[3])
118 {
119         BoundVert *ans = (BoundVert *) MEM_callocN(sizeof(BoundVert), "BoundVert");
120         copy_v3_v3(ans->nv.co, co);
121         if (!vm->boundstart) {
122                 ans->index = 0;
123                 vm->boundstart = ans;
124                 ans->next = ans->prev = ans;
125         }
126         else {
127                 BoundVert *tail = vm->boundstart->prev;
128                 ans->index = tail->index + 1;
129                 ans->prev = tail;
130                 ans->next = vm->boundstart;
131                 tail->next = ans;
132                 vm->boundstart->prev = ans;
133         }
134         vm->count++;
135         return ans;
136 }
137
138 /* Mesh verts are indexed (i, j, k) where
139  * i = boundvert index (0 <= i < nv)
140  * j = ring index (0 <= j <= ns2)
141  * k = segment index (0 <= k <= ns)
142  * Not all of these are used, and some will share BMVerts */
143 static NewVert *mesh_vert(VMesh *vm, int i, int j, int k)
144 {
145         int nj = (vm->seg / 2) + 1;
146         int nk = vm->seg + 1;
147
148         return &vm->mesh[i * nk * nj  + j * nk + k];
149 }
150
151 static void create_mesh_bmvert(BMesh *bm, VMesh *vm, int i, int j, int k, BMVert *eg)
152 {
153         NewVert *nv = mesh_vert(vm, i, j, k);
154         nv->v = BM_vert_create(bm, nv->co, eg);
155 }
156
157 static void copy_mesh_vert(VMesh *vm, int ito, int jto, int kto,
158                            int ifrom, int jfrom, int kfrom)
159 {
160         NewVert *nvto, *nvfrom;
161
162         nvto = mesh_vert(vm, ito, jto, kto);
163         nvfrom = mesh_vert(vm, ifrom, jfrom, kfrom);
164         nvto->v = nvfrom->v;
165         copy_v3_v3(nvto->co, nvfrom->co);
166 }
167
168 /* find the EdgeHalf in bv's array that has edge bme */
169 static EdgeHalf *find_edge_half(BevVert *bv, BMEdge *bme)
170 {
171         int i;
172
173         for (i = 0; i < bv->edgecount; i++) {
174                 if (bv->edges[i].e == bme)
175                         return &bv->edges[i];
176         }
177         return NULL;
178 }
179
180 /* Return the next EdgeHalf after from_e that is beveled.
181  * If from_e is NULL, find the first beveled edge. */
182 static EdgeHalf *next_bev(BevVert *bv, EdgeHalf *from_e)
183 {
184         EdgeHalf *e;
185
186         if (from_e == NULL)
187                 from_e = &bv->edges[bv->edgecount - 1];
188         e = from_e;
189         do {
190                 if (e->isbev)
191                         return e;
192                 e = e->next;
193         } while (e != from_e);
194         return NULL;
195 }
196
197 /* find the BevVert corresponding to BMVert bmv */
198 static BevVert *find_bevvert(BevelParams *bp, BMVert *bmv)
199 {
200         BevVert *bv;
201
202         for (bv = bp->vertList.first; bv; bv = bv->next) {
203                 if (bv->v == bmv)
204                         return bv;
205         }
206         return NULL;
207 }
208
209 /* Return a good respresentative face (for materials, etc.) for faces
210  * created around/near BoundVert v */
211 static BMFace *boundvert_rep_face(BoundVert *v)
212 {
213         BMFace *fans = NULL;
214         BMFace *firstf = NULL;
215         BMEdge *e1, *e2;
216         BMFace *f1, *f2;
217         BMIter iter1, iter2;
218
219         BLI_assert(v->efirst != NULL && v->elast != NULL);
220         e1 = v->efirst->e;
221         e2 = v->elast->e;
222         BM_ITER_ELEM (f1, &iter1, e1, BM_FACES_OF_EDGE) {
223                 if (!firstf)
224                         firstf = f1;
225                 BM_ITER_ELEM (f2, &iter2, e2, BM_FACES_OF_EDGE) {
226                         if (f1 == f2) {
227                                 fans = f1;
228                                 break;
229                         }
230                 }
231         }
232         if (!fans)
233                 fans = firstf;
234
235         return fans;
236 }
237
238 /* Make ngon from verts alone.
239  * Make sure to properly copy face attributes and do custom data interpolation from
240  * example face, facerep. */
241 static BMFace *bev_create_ngon(BMesh *bm, BMVert **vert_arr, int totv, BMFace *facerep)
242 {
243         BMIter iter;
244         BMLoop *l;
245         BMFace *f;
246
247         if (totv == 3) {
248                 f = BM_face_create_quad_tri(bm,
249                                             vert_arr[0], vert_arr[1], vert_arr[2], NULL, facerep, 0);
250         }
251         else if (totv == 4) {
252                 f = BM_face_create_quad_tri(bm,
253                                             vert_arr[0], vert_arr[1], vert_arr[2], vert_arr[3], facerep, 0);
254         }
255         else {
256                 int i;
257                 BMEdge *e;
258                 BMEdge **ee = NULL;
259                 BLI_array_staticdeclare(ee, 30);
260
261                 for (i = 0; i < totv; i++) {
262                         e = BM_edge_create(bm, vert_arr[i], vert_arr[(i + 1) % totv], NULL, TRUE);
263                         BLI_array_append(ee, e);
264                 }
265                 f = BM_face_create_ngon(bm, vert_arr[0], vert_arr[1], ee, totv, FALSE);
266                 BLI_array_free(ee);
267         }
268         if (facerep && f) {
269                 int has_mdisps = CustomData_has_layer(&bm->ldata, CD_MDISPS);
270                 BM_elem_attrs_copy(bm, bm, facerep, f);
271                 BM_ITER_ELEM (l, &iter, f, BM_LOOPS_OF_FACE) {
272                         BM_loop_interp_from_face(bm, l, facerep, TRUE, TRUE);
273                         if (has_mdisps)
274                                 BM_loop_interp_multires(bm, l, facerep);
275                 }
276         }
277         return f;
278 }
279
280 static BMFace *bev_create_quad_tri(BMesh *bm, BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4,
281                                    BMFace *facerep)
282 {
283         BMVert *varr[4];
284
285         varr[0] = v1;
286         varr[1] = v2;
287         varr[2] = v3;
288         varr[3] = v4;
289         return bev_create_ngon(bm, varr, v4 ? 4 : 3, facerep);
290 }
291
292 /*
293  * Calculate the meeting point between the offset edges for e1 and e2, putting answer in meetco.
294  * e1 and e2 share vertex v and face f (may be NULL) and viewed from the normal side of
295  * the bevel vertex,  e1 precedes e2 in CCW order.
296  * If on_right is true, offset edge is on right of both edges, where e1 enters v and
297  * e2 leave it. If on_right is false, then the offset edge is on the left.
298  * When offsets are equal, the new point is on the edge bisector, with length offset/sin(angle/2),
299  * but if the offsets are not equal (allowing for this, as bevel modifier has edge weights that may
300  * lead to different offsets) then meeting point can be found be intersecting offset lines.
301  */
302 static void offset_meet(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, BMFace *f,
303                         int on_right, float meetco[3])
304 {
305         float dir1[3], dir2[3], norm_v[3], norm_perp1[3], norm_perp2[3],
306               off1a[3], off1b[3], off2a[3], off2b[3], isect2[3];
307
308         /* get direction vectors for two offset lines */
309         sub_v3_v3v3(dir1, v->co, BM_edge_other_vert(e1->e, v)->co);
310         sub_v3_v3v3(dir2, BM_edge_other_vert(e2->e, v)->co, v->co);
311
312         /* get normal to plane where meet point should be */
313         cross_v3_v3v3(norm_v, dir2, dir1);
314         normalize_v3(norm_v);
315         if (!on_right)
316                 negate_v3(norm_v);
317         if (is_zero_v3(norm_v)) {
318                 /* special case: e1 and e2 are parallel; put offset point perp to both, from v.
319                  * need to find a suitable plane.
320                  * if offsets are different, we're out of luck: just use e1->offset */
321                 if (f)
322                         copy_v3_v3(norm_v, f->no);
323                 else
324                         copy_v3_v3(norm_v, v->no);
325                 cross_v3_v3v3(norm_perp1, dir1, norm_v);
326                 normalize_v3(norm_perp1);
327                 copy_v3_v3(off1a, v->co);
328                 madd_v3_v3fl(off1a, norm_perp1, e1->offset);
329                 copy_v3_v3(meetco, off1a);
330         }
331         else {
332                 /* get vectors perp to each edge, perp to norm_v, and pointing into face */
333                 if (f) {
334                         copy_v3_v3(norm_v, f->no);
335                         normalize_v3(norm_v);
336                 }
337                 cross_v3_v3v3(norm_perp1, dir1, norm_v);
338                 cross_v3_v3v3(norm_perp2, dir2, norm_v);
339                 normalize_v3(norm_perp1);
340                 normalize_v3(norm_perp2);
341
342                 /* get points that are offset distances from each line, then another point on each line */
343                 copy_v3_v3(off1a, v->co);
344                 madd_v3_v3fl(off1a, norm_perp1, e1->offset);
345                 add_v3_v3v3(off1b, off1a, dir1);
346                 copy_v3_v3(off2a, v->co);
347                 madd_v3_v3fl(off2a, norm_perp2, e2->offset);
348                 add_v3_v3v3(off2b, off2a, dir2);
349
350                 /* intersect the lines; by construction they should be on the same plane and not parallel */
351                 if (!isect_line_line_v3(off1a, off1b, off2a, off2b, meetco, isect2)) {
352                         BLI_assert(!"offset_meet failure");
353                         copy_v3_v3(meetco, off1a);  /* just to do something */
354                 }
355         }
356 }
357
358 /* Like offset_meet, but here f1 and f2 must not be NULL and give the
359  * planes in which to run the offset lines.  They may not meet exactly,
360  * but the line intersection routine will find the closest approach point. */
361 static void offset_in_two_planes(EdgeHalf *e1, EdgeHalf *e2, BMVert *v,
362                                  BMFace *f1, BMFace *f2, float meetco[3])
363 {
364         float dir1[3], dir2[3], norm_perp1[3], norm_perp2[3],
365               off1a[3], off1b[3], off2a[3], off2b[3], isect2[3];
366
367         BLI_assert(f1 != NULL && f2 != NULL);
368
369         /* get direction vectors for two offset lines */
370         sub_v3_v3v3(dir1, v->co, BM_edge_other_vert(e1->e, v)->co);
371         sub_v3_v3v3(dir2, BM_edge_other_vert(e2->e, v)->co, v->co);
372
373         /* get directions into offset planes */
374         cross_v3_v3v3(norm_perp1, dir1, f1->no);
375         normalize_v3(norm_perp1);
376         cross_v3_v3v3(norm_perp2, dir2, f2->no);
377         normalize_v3(norm_perp2);
378
379         /* get points that are offset distances from each line, then another point on each line */
380         copy_v3_v3(off1a, v->co);
381         madd_v3_v3fl(off1a, norm_perp1, e1->offset);
382         add_v3_v3v3(off1b, off1a, dir1);
383         copy_v3_v3(off2a, v->co);
384         madd_v3_v3fl(off2a, norm_perp2, e2->offset);
385         add_v3_v3v3(off2b, off2a, dir2);
386
387         if (!isect_line_line_v3(off1a, off1b, off2a, off2b, meetco, isect2)) {
388                 /* lines are parallel; off1a is a good meet point */
389                 copy_v3_v3(meetco, off1a);
390         }
391 }
392
393 /* Offset by e->offset in plane with normal plane_no, on left if left==TRUE,
394  * else on right.  If no is NULL, choose an arbitrary plane different
395  * from eh's direction. */
396 static void offset_in_plane(EdgeHalf *e, float plane_no[3], int left, float r[3])
397 {
398         float dir[3], no[3];
399         BMVert *v;
400
401         v = e->isrev ? e->e->v1 : e->e->v2;
402
403         sub_v3_v3v3(dir, BM_edge_other_vert(e->e, v)->co, v->co);
404         normalize_v3(dir);
405         if (plane_no) {
406                 copy_v3_v3(no, plane_no);
407         }
408         else {
409                 zero_v3(no);
410                 if (fabs(dir[0]) < fabs(dir[1]))
411                         no[0] = 1.0f;
412                 else
413                         no[1] = 1.0f;
414         }
415         if (left)
416                 cross_v3_v3v3(r, no, dir);
417         else
418                 cross_v3_v3v3(r, dir, no);
419         normalize_v3(r);
420         mul_v3_fl(r, e->offset);
421 }
422
423 /* Calculate coordinates of a point a distance d from v on e->e and return it in slideco */
424 static void slide_dist(EdgeHalf *e, BMVert *v, float d, float slideco[3])
425 {
426         float dir[3], len;
427
428         sub_v3_v3v3(dir, v->co, BM_edge_other_vert(e->e, v)->co);
429         len = len_v3(dir);
430         normalize_v3(dir);
431         if (d > len)
432                 d = len - (float)(50 * BEVEL_EPSILON);
433         copy_v3_v3(slideco, v->co);
434         madd_v3_v3fl(slideco, dir, -d);
435 }
436
437 /* Calculate the point on e where line (co_a, co_b) comes closest to and return it in projco */
438 static void project_to_edge(BMEdge *e, float co_a[3], float co_b[3], float projco[3])
439 {
440         float otherco[3];
441
442         if (!isect_line_line_v3(e->v1->co, e->v2->co, co_a, co_b,
443                                 projco, otherco)) {
444                 BLI_assert(!"project meet failure");
445                 copy_v3_v3(projco, e->v1->co);
446         }
447 }
448
449
450 /* return 1 if a and b are in CCW order on the normal side of f,
451  * and -1 if they are reversed, and 0 if there is no shared face f */
452 static int bev_ccw_test(BMEdge *a, BMEdge *b, BMFace *f)
453 {
454         BMLoop *la, *lb;
455
456         if (!f)
457                 return 0;
458         la = BM_face_edge_share_loop(f, a);
459         lb = BM_face_edge_share_loop(f, b);
460         if (!la || !lb)
461                 return 0;
462         return lb->next == la ? 1 : -1;
463 }
464
465 /*
466  * calculation of points on the round profile
467  * r - result, coordinate of point on round profile
468  * method:
469  * Inscribe a circle in angle va - v -vb
470  * such that it touches the arms at offset from v.
471  * Rotate the center-va segment by (i/n) of the
472  * angle va - center -vb, and put the endpoint
473  * of that segment in r.
474  */
475 static void get_point_on_round_profile(float r[3], float offset, int i, int count,
476                                        float va[3], float v[3], float vb[3])
477 {
478         float vva[3], vvb[3], angle, center[3], rv[3], axis[3], co[3];
479
480         sub_v3_v3v3(vva, va, v);
481         sub_v3_v3v3(vvb, vb, v);
482         normalize_v3(vva);
483         normalize_v3(vvb);
484         angle = angle_v3v3(vva, vvb);
485
486         add_v3_v3v3(center, vva, vvb);
487         normalize_v3(center);
488         mul_v3_fl(center, offset * (1.0f / cosf(0.5f * angle)));
489         add_v3_v3(center, v);           /* coordinates of the center of the inscribed circle */
490
491
492         sub_v3_v3v3(rv, va, center);    /* radius vector */
493
494
495         sub_v3_v3v3(co, v, center);
496         cross_v3_v3v3(axis, rv, co);    /* calculate axis */
497
498         sub_v3_v3v3(vva, va, center);
499         sub_v3_v3v3(vvb, vb, center);
500         angle = angle_v3v3(vva, vvb);
501
502         rotate_v3_v3v3fl(co, rv, axis, angle * (float)(i) / (float)(count));
503
504         add_v3_v3(co, center);
505         copy_v3_v3(r, co);
506 }
507
508 /*
509  * Find the point (i/n) of the way around the round profile for e,
510  * where start point is va, midarc point is vmid, and end point is vb.
511  * Return the answer in profileco.
512  * Method:
513  * Adjust va and vb (along edge direction) so that they are perpendicular
514  * to edge at v, then use get_point_on_round_profile, then project
515  * back onto original va - vmid - vb plane.
516  * If va, vmid, and vb are all on the same plane, just interpolate between va and vb.
517  */
518 static void get_point_on_round_edge(EdgeHalf *e, int i,
519                                     float va[3], float vmid[3], float vb[3], float profileco[3])
520 {
521         float vva[3], vvb[3],  point[3], dir[3], vaadj[3], vbadj[3], p2[3], pn[3];
522         int n = e->seg;
523
524         sub_v3_v3v3(vva, va, vmid);
525         sub_v3_v3v3(vvb, vb, vmid);
526         if (e->isrev)
527                 sub_v3_v3v3(dir, e->e->v1->co, e->e->v2->co);
528         else
529                 sub_v3_v3v3(dir, e->e->v2->co, e->e->v1->co);
530         normalize_v3(dir);
531         if (fabsf(angle_v3v3(vva, vvb) - (float)M_PI) > (float)BEVEL_EPSILON) {
532                 copy_v3_v3(vaadj, va);
533                 madd_v3_v3fl(vaadj, dir, -len_v3(vva) * cosf(angle_v3v3(vva, dir)));
534                 copy_v3_v3(vbadj, vb);
535                 madd_v3_v3fl(vbadj, dir, -len_v3(vvb) * cosf(angle_v3v3(vvb, dir)));
536
537                 get_point_on_round_profile(point, e->offset, i, n, vaadj, vmid, vbadj);
538
539                 add_v3_v3v3(p2, point, dir);
540                 cross_v3_v3v3(pn, vva, vvb);
541                 if (!isect_line_plane_v3(profileco, point, p2, vmid, pn, 0)) {
542                         /* TODO: track down why this sometimes fails */
543                         copy_v3_v3(profileco, point);
544                 }
545         }
546         else {
547                 /* planar case */
548                 interp_v3_v3v3(profileco, va, vb, (float) i / (float) n);
549         }
550 }
551
552 static void mid_v3_v3v3v3(float v[3], const float v1[3], const float v2[3], const float v3[3])
553 {
554         v[0] = (v1[0] + v2[0] + v3[0]) / 3.0f;
555         v[1] = (v1[1] + v2[1] + v3[1]) / 3.0f;
556         v[2] = (v1[2] + v2[2] + v3[2]) / 3.0f;
557 }
558
559 /* Make a circular list of BoundVerts for bv, each of which has the coordinates
560  * of a vertex on the the boundary of the beveled vertex bv->v.
561  * Also decide on the mesh pattern that will be used inside the boundary.
562  * Doesn't make the actual BMVerts */
563 static void build_boundary(BevVert *bv)
564 {
565         EdgeHalf *efirst, *e;
566         BoundVert *v;
567         VMesh *vm;
568         float co[3], *no;
569         float lastd;
570
571         e = efirst = next_bev(bv, NULL);
572         vm = bv->vmesh;
573
574         BLI_assert(bv->edgecount >= 2);  /* since bevel edges incident to 2 faces */
575
576         if (bv->edgecount == 2 && bv->selcount == 1) {
577                 /* special case: beveled edge meets non-beveled one at valence 2 vert */
578                 no = e->fprev ? e->fprev->no : (e->fnext ? e->fnext->no : NULL);
579                 offset_in_plane(e, no, TRUE, co);
580                 v = add_new_bound_vert(vm, co);
581                 v->efirst = v->elast = v->ebev = e;
582                 e->leftv = v;
583                 no = e->fnext ? e->fnext->no : (e->fprev ? e->fprev->no : NULL);
584                 offset_in_plane(e, no, FALSE, co);
585                 v = add_new_bound_vert(vm, co);
586                 v->efirst = v->elast = e;
587                 e->rightv = v;
588                 /* make artifical extra point along unbeveled edge, and form triangle */
589                 slide_dist(e->next, bv->v, e->offset, co);
590                 v = add_new_bound_vert(vm, co);
591                 v->efirst = v->elast = e->next;
592                 vm->mesh_kind = M_POLY;
593                 return;
594         }
595
596         lastd = e->offset;
597         vm->boundstart = NULL;
598         do {
599                 if (e->isbev) {
600                         /* handle only left side of beveled edge e here: next iteration should do right side */
601                         if (e->prev->isbev) {
602                                 BLI_assert(e->prev != e);  /* see: wire edge special case */
603                                 offset_meet(e->prev, e, bv->v, e->fprev, TRUE, co);
604                                 v = add_new_bound_vert(vm, co);
605                                 v->efirst = e->prev;
606                                 v->elast = v->ebev = e;
607                                 e->leftv = v;
608                                 e->prev->rightv = v;
609                         }
610                         else {
611                                 /* e->prev is not beveled */
612                                 if (e->prev->prev->isbev) {
613                                         BLI_assert(e->prev->prev != e); /* see: edgecount 2, selcount 1 case */
614                                         /* find meet point between e->prev->prev and e and attach e->prev there */
615                                         /* TODO: fix case when one or both faces in following are NULL */
616                                         offset_in_two_planes(e->prev->prev, e, bv->v,
617                                                              e->prev->prev->fnext, e->fprev, co);
618                                         v = add_new_bound_vert(vm, co);
619                                         v->efirst = e->prev->prev;
620                                         v->elast = v->ebev = e;
621                                         e->leftv = v;
622                                         e->prev->leftv = v;
623                                         e->prev->prev->rightv = v;
624                                 }
625                                 else {
626                                         /* neither e->prev nor e->prev->prev are beveled: make on-edge on e->prev */
627                                         offset_meet(e->prev, e, bv->v, e->fprev, TRUE, co);
628                                         v = add_new_bound_vert(vm, co);
629                                         v->efirst = e->prev;
630                                         v->elast = v->ebev = e;
631                                         e->leftv = v;
632                                         e->prev->leftv = v;
633                                 }
634                         }
635                         lastd = len_v3v3(bv->v->co, v->nv.co);
636                 }
637                 else {
638                         /* e is not beveled */
639                         if (e->next->isbev) {
640                                 /* next iteration will place e between beveled previous and next edges */
641                                 e = e->next;
642                                 continue;
643                         }
644                         if (e->prev->isbev) {
645                                 /* on-edge meet between e->prev and e */
646                                 offset_meet(e->prev, e, bv->v, e->fprev, TRUE, co);
647                                 v = add_new_bound_vert(vm, co);
648                                 v->efirst = e->prev;
649                                 v->elast = e;
650                                 e->leftv = v;
651                                 e->prev->rightv = v;
652                         }
653                         else {
654                                 /* None of e->prev, e, e->next are beveled.
655                                  * could either leave alone or add slide points to make
656                                  * one polygon around bv->v.  For now, we choose latter.
657                                  * Could slide to make an even bevel plane but for now will
658                                  * just use last distance a meet point moved from bv->v. */
659                                 slide_dist(e, bv->v, lastd, co);
660                                 v = add_new_bound_vert(vm, co);
661                                 v->efirst = v->elast = e;
662                                 e->leftv = v;
663                         }
664                 }
665                 e = e->next;
666         } while (e != efirst);
667
668         BLI_assert(vm->count >= 2);
669         if (vm->count == 2 && bv->edgecount == 3)
670                 vm->mesh_kind = M_NONE;
671         else if (efirst->seg == 1 || bv->selcount == 1)
672                 vm->mesh_kind = M_POLY;
673         else
674                 vm->mesh_kind = M_ADJ;
675         /* TODO: if vm->count == 4 and bv->selcount == 4, use M_CROSS pattern */
676 }
677
678 /*
679  * Given that the boundary is built and the boundary BMVerts have been made,
680  * calculate the positions of the interior mesh points for the M_ADJ pattern,
681  * then make the BMVerts and the new faces. */
682 static void bevel_build_rings(BMesh *bm, BevVert *bv)
683 {
684         int k, ring, i, n, ns, ns2, nn;
685         VMesh *vm = bv->vmesh;
686         BoundVert *v, *vprev, *vnext;
687         NewVert *nv, *nvprev, *nvnext;
688         BMVert *bmv, *bmv1, *bmv2, *bmv3, *bmv4;
689         BMFace *f;
690         float co[3], coa[3], cob[3], midco[3];
691
692         n = vm->count;
693         ns = vm->seg;
694         ns2 = ns / 2;
695         BLI_assert(n > 2 && ns > 1);
696         /* Make initial rings, going between points on neighbors.
697          * After this loop, will have coords for all (i, r, k) where
698          * BoundVert for i has a bevel, 0 <= r <= ns2, 0 <= k <= ns */
699         for (ring = 1; ring <= ns2; ring++) {
700                 v = vm->boundstart;
701                 do {
702                         i = v->index;
703                         if (v->ebev) {
704                                 /* get points coords of points a and b, on outer rings
705                                  * of prev and next edges, k away from this edge */
706                                 vprev = v->prev;
707                                 vnext = v->next;
708
709                                 if (vprev->ebev)
710                                         nvprev = mesh_vert(vm, vprev->index, 0, ns - ring);
711                                 else
712                                         nvprev = mesh_vert(vm, vprev->index, 0, ns);
713                                 copy_v3_v3(coa, nvprev->co);
714                                 nv = mesh_vert(vm, i, ring, 0);
715                                 copy_v3_v3(nv->co, coa);
716                                 nv->v = nvprev->v;
717
718                                 if (vnext->ebev)
719                                         nvnext = mesh_vert(vm, vnext->index, 0, ring);
720                                 else
721                                         nvnext = mesh_vert(vm, vnext->index, 0, 0);
722                                 copy_v3_v3(cob, nvnext->co);
723                                 nv = mesh_vert(vm, i, ring, ns);
724                                 copy_v3_v3(nv->co, cob);
725                                 nv->v = nvnext->v;
726
727                                 /* TODO: better calculation of new midarc point? */
728                                 project_to_edge(v->ebev->e, coa, cob, midco);
729
730                                 for (k = 1; k < ns; k++) {
731                                         get_point_on_round_edge(v->ebev, k, coa, midco, cob, co);
732                                         copy_v3_v3(mesh_vert(vm, i, ring, k)->co, co);
733                                 }
734                         }
735                         v = v->next;
736                 } while (v != vm->boundstart);
737         }
738
739         /* Now make sure cross points of rings share coordinates and vertices.
740          * After this loop, will have BMVerts for all (i, r, k) where
741          * i is for a BoundVert that is beveled and has either a predecessor or
742          * successor BoundVert beveled too, and
743          * for odd ns: 0 <= r <= ns2, 0 <= k <= ns
744          * for even ns: 0 <= r < ns2, 0 <= k <= ns except k=ns2 */
745         v = vm->boundstart;
746         do {
747                 i = v->index;
748                 if (v->ebev) {
749                         vprev = v->prev;
750                         vnext = v->next;
751                         if (vprev->ebev) {
752                                 for (ring = 1; ring <= ns2; ring++) {
753                                         for (k = 1; k <= ns2; k++) {
754                                                 if (ns % 2 == 0 && (k == ns2 || ring == ns2))
755                                                         continue;  /* center line is special case: do after the rest are done */
756                                                 nv = mesh_vert(vm, i, ring, k);
757                                                 nvprev = mesh_vert(vm, vprev->index, k, ns - ring);
758                                                 mid_v3_v3v3(co, nv->co, nvprev->co);
759                                                 copy_v3_v3(nv->co, co);
760                                                 BLI_assert(nv->v == NULL && nvprev->v == NULL);
761                                                 create_mesh_bmvert(bm, vm, i, ring, k, bv->v);
762                                                 copy_mesh_vert(vm, vprev->index, k, ns - ring, i, ring, k);
763                                         }
764                                 }
765                                 if (!vprev->prev->ebev) {
766                                         for (ring = 1; ring <= ns2; ring++) {
767                                                 for (k = 1; k <= ns2; k++) {
768                                                         if (ns % 2 == 0 && (k == ns2 || ring == ns2))
769                                                                 continue;
770                                                         create_mesh_bmvert(bm, vm, vprev->index, ring, k, bv->v);
771                                                 }
772                                         }
773                                 }
774                                 if (!vnext->ebev) {
775                                         for (ring = 1; ring <= ns2; ring++) {
776                                                 for (k = ns - ns2; k < ns; k++) {
777                                                         if (ns % 2 == 0 && (k == ns2 || ring == ns2))
778                                                                 continue;
779                                                         create_mesh_bmvert(bm, vm, i, ring, k, bv->v);
780                                                 }
781                                         }
782                                 }
783                         }
784                 }
785                 v = v->next;
786         } while (v != vm->boundstart);
787
788         if (ns % 2 == 0) {
789                 /* Do special case center lines.
790                  * This loop makes verts for (i, ns2, k) for 1 <= k <= ns-1, k!=ns2
791                  * and for (i, r, ns2) for 1 <= r <= ns2-1,
792                  * whenever i is in a sequence of at least two beveled verts */
793                 v = vm->boundstart;
794                 do {
795                         i = v->index;
796                         if (v->ebev) {
797                                 vprev = v->prev;
798                                 vnext = v->next;
799                                 for (k = 1; k < ns2; k++) {
800                                         nv = mesh_vert(vm, i, k, ns2);
801                                         if (vprev->ebev)
802                                                 nvprev = mesh_vert(vm, vprev->index, ns2, ns - k);
803                                         if (vnext->ebev)
804                                                 nvnext = mesh_vert(vm, vnext->index, ns2, k);
805                                         if (vprev->ebev && vnext->ebev) {
806                                                 mid_v3_v3v3v3(co, nvprev->co, nv->co, nvnext->co);
807                                                 copy_v3_v3(nv->co, co);
808                                                 create_mesh_bmvert(bm, vm, i, k, ns2, bv->v);
809                                                 copy_mesh_vert(vm, vprev->index, ns2, ns - k, i, k, ns2);
810                                                 copy_mesh_vert(vm, vnext->index, ns2, k, i, k, ns2);
811
812                                         }
813                                         else if (vprev->ebev) {
814                                                 mid_v3_v3v3(co, nvprev->co, nv->co);
815                                                 copy_v3_v3(nv->co, co);
816                                                 create_mesh_bmvert(bm, vm, i, k, ns2, bv->v);
817                                                 copy_mesh_vert(vm, vprev->index, ns2, ns - k, i, k, ns2);
818
819                                                 create_mesh_bmvert(bm, vm, i, ns2, ns - k, bv->v);
820                                         }
821                                         else if (vnext->ebev) {
822                                                 mid_v3_v3v3(co, nv->co, nvnext->co);
823                                                 copy_v3_v3(nv->co, co);
824                                                 create_mesh_bmvert(bm, vm, i, k, ns2, bv->v);
825                                                 copy_mesh_vert(vm, vnext->index, ns2, k, i, k, ns2);
826
827                                                 create_mesh_bmvert(bm, vm, i, ns2, k, bv->v);
828                                         }
829                                 }
830                         }
831                         v = v->next;
832                 } while (v != vm->boundstart);
833
834                 /* center point need to be average of all centers of rings */
835                 /* TODO: this is wrong if not all verts have ebev: could have
836                  * several disconnected sections of mesh. */
837                 zero_v3(midco);
838                 nn = 0;
839                 v = vm->boundstart;
840                 do {
841                         i = v->index;
842                         if (v->ebev) {
843                                 nv = mesh_vert(vm, i, ns2, ns2);
844                                 add_v3_v3(midco, nv->co);
845                                 nn++;
846                         }
847                         v = v->next;
848                 } while (v != vm->boundstart);
849                 mul_v3_fl(midco, 1.0f / nn);
850                 bmv = BM_vert_create(bm, midco, NULL);
851                 v = vm->boundstart;
852                 do {
853                         i = v->index;
854                         if (v->ebev) {
855                                 nv = mesh_vert(vm, i, ns2, ns2);
856                                 copy_v3_v3(nv->co, midco);
857                                 nv->v = bmv;
858                         }
859                         v = v->next;
860                 } while (v != vm->boundstart);
861         }
862
863         /* Make the ring quads */
864         for (ring = 0; ring < ns2; ring++) {
865                 v = vm->boundstart;
866                 do {
867                         i = v->index;
868                         f = boundvert_rep_face(v);
869                         if (v->ebev && (v->prev->ebev || v->next->ebev)) {
870                                 for (k = 0; k < ns2 + (ns % 2); k++) {
871                                         bmv1 = mesh_vert(vm, i, ring, k)->v;
872                                         bmv2 = mesh_vert(vm, i, ring, k + 1)->v;
873                                         bmv3 = mesh_vert(vm, i, ring + 1, k + 1)->v;
874                                         bmv4 = mesh_vert(vm, i, ring + 1, k)->v;
875                                         BLI_assert(bmv1 && bmv2 && bmv3 && bmv4);
876                                         if (bmv3 == bmv4 || bmv1 == bmv4)
877                                                 bmv4 = NULL;
878                                         bev_create_quad_tri(bm, bmv1, bmv2, bmv3, bmv4, f);
879                                 }
880                         }
881                         else if (v->prev->ebev && v->prev->prev->ebev) {
882                                 /* finish off a sequence of beveled edges */
883                                 i = v->prev->index;
884                                 f = boundvert_rep_face(v->prev);
885                                 for (k = ns2 + (ns % 2); k < ns; k++) {
886                                         bmv1 = mesh_vert(vm, i, ring, k)->v;
887                                         bmv2 = mesh_vert(vm, i, ring, k + 1)->v;
888                                         bmv3 = mesh_vert(vm, i, ring + 1, k + 1)->v;
889                                         bmv4 = mesh_vert(vm, i, ring + 1, k)->v;
890                                         BLI_assert(bmv1 && bmv2 && bmv3 && bmv4);
891                                         if (bmv2 == bmv3) {
892                                                 bmv3 = bmv4;
893                                                 bmv4 = NULL;
894                                         }
895                                         bev_create_quad_tri(bm, bmv1, bmv2, bmv3, bmv4, f);
896                                 }
897                         }
898                         v = v->next;
899                 } while (v != vm->boundstart);
900         }
901
902         /* Make center ngon if odd number of segments and fully beveled */
903         if (ns % 2 == 1 && vm->count == bv->selcount) {
904                 BMVert **vv = NULL;
905                 BLI_array_declare(vv);
906
907                 v = vm->boundstart;
908                 do {
909                         i = v->index;
910                         BLI_assert(v->ebev);
911                         BLI_array_append(vv, mesh_vert(vm, i, ns2, ns2)->v);
912                         v = v->next;
913                 } while (v != vm->boundstart);
914                 f = boundvert_rep_face(vm->boundstart);
915                 bev_create_ngon(bm, vv, BLI_array_count(vv), f);
916
917                 BLI_array_free(vv);
918         }
919
920         /* Make 'rest-of-vmesh' polygon if not fully beveled */
921         if (vm->count > bv->selcount) {
922                 int j;
923                 BMVert **vv = NULL;
924                 BLI_array_declare(vv);
925
926                 v = vm->boundstart;
927                 f = boundvert_rep_face(v);
928                 j = 0;
929                 do {
930                         i = v->index;
931                         if (v->ebev) {
932                                 if (!v->prev->ebev) {
933                                         for (k = 0; k < ns2; k++) {
934                                                 bmv1 = mesh_vert(vm, i, ns2, k)->v;
935                                                 if (!bmv1)
936                                                         bmv1 = mesh_vert(vm, i, 0, k)->v;
937                                                 if (!(j > 0 && bmv1 == vv[j - 1])) {
938                                                         BLI_assert(bmv1 != NULL);
939                                                         BLI_array_append(vv, bmv1);
940                                                         j++;
941                                                 }
942                                         }
943                                 }
944                                 bmv1 = mesh_vert(vm, i, ns2, ns2)->v;
945                                 if (!bmv1)
946                                         bmv1 = mesh_vert(vm, i, 0, ns2)->v;
947                                 if (!(j > 0 && bmv1 == vv[j - 1])) {
948                                         BLI_assert(bmv1 != NULL);
949                                         BLI_array_append(vv, bmv1);
950                                         j++;
951                                 }
952                                 if (!v->next->ebev) {
953                                         for (k = ns - ns2; k < ns; k++) {
954                                                 bmv1 = mesh_vert(vm, i, ns2, k)->v;
955                                                 if (!bmv1)
956                                                         bmv1 = mesh_vert(vm, i, 0, k)->v;
957                                                 if (!(j > 0 && bmv1 == vv[j - 1])) {
958                                                         BLI_assert(bmv1 != NULL);
959                                                         BLI_array_append(vv, bmv1);
960                                                         j++;
961                                                 }
962                                         }
963                                 }
964                         }
965                         else {
966                                 BLI_assert(mesh_vert(vm, i, 0, 0)->v != NULL);
967                                 BLI_array_append(vv, mesh_vert(vm, i, 0, 0)->v);
968                                 j++;
969                         }
970                         v = v->next;
971                 } while (v != vm->boundstart);
972                 if (vv[0] == vv[j - 1])
973                         j--;
974                 bev_create_ngon(bm, vv, j, f);
975
976                 BLI_array_free(vv);
977         }
978 }
979
980 static void bevel_build_poly(BMesh *bm, BevVert *bv)
981 {
982         int n, k;
983         VMesh *vm = bv->vmesh;
984         BoundVert *v;
985         BMVert **vv = NULL;
986         BLI_array_declare(vv);
987
988         v = vm->boundstart;
989         n = 0;
990         do {
991                 /* accumulate vertices for vertex ngon */
992                 BLI_array_append(vv, v->nv.v);
993                 n++;
994                 if (v->ebev && v->ebev->seg > 1) {
995                         for (k = 1; k < v->ebev->seg; k++) {
996                                 BLI_array_append(vv, mesh_vert(vm, v->index, 0, k)->v);
997                                 n++;
998                         }
999                 }
1000                 v = v->next;
1001         } while (v != vm->boundstart);
1002         if (n > 2)
1003                 bev_create_ngon(bm, vv, n, boundvert_rep_face(v));
1004         BLI_array_free(vv);
1005 }
1006
1007 /* Given that the boundary is built, now make the actual BMVerts
1008  * for the boundary and the interior of the vertex mesh. */
1009 static void build_vmesh(BMesh *bm, BevVert *bv)
1010 {
1011         VMesh *vm = bv->vmesh;
1012         BoundVert *v, *weld1, *weld2;
1013         int n, ns, ns2, i, k, weld;
1014         float *va, *vb, co[3], midco[3];
1015
1016         n = vm->count;
1017         ns = vm->seg;
1018         ns2 = ns / 2;
1019
1020         vm->mesh = (NewVert *)MEM_callocN(n * (ns2 + 1) * (ns + 1) * sizeof(NewVert), "NewVert");
1021
1022         /* special case: two beveled ends welded together */
1023         weld = (bv->selcount == 2) && (vm->count == 2);
1024         weld1 = weld2 = NULL;   /* will hold two BoundVerts involved in weld */
1025
1026         /* make (i, 0, 0) mesh verts for all i */
1027         v = vm->boundstart;
1028         do {
1029                 i = v->index;
1030                 copy_v3_v3(mesh_vert(vm, i, 0, 0)->co, v->nv.co);
1031                 create_mesh_bmvert(bm, vm, i, 0, 0, bv->v);
1032                 v->nv.v = mesh_vert(vm, i, 0, 0)->v;
1033                 if (weld && v->ebev) {
1034                         if (!weld1)
1035                                 weld1 = v;
1036                         else
1037                                 weld2 = v;
1038                 }
1039                 v = v->next;
1040         } while (v != vm->boundstart);
1041
1042         /* copy other ends to (i, 0, ns) for all i, and fill in profiles for beveled edges */
1043         v = vm->boundstart;
1044         do {
1045                 i = v->index;
1046                 copy_mesh_vert(vm, i, 0, ns, v->next->index, 0, 0);
1047                 if (v->ebev) {
1048                         va = mesh_vert(vm, i, 0, 0)->co;
1049                         vb = mesh_vert(vm, i, 0, ns)->co;
1050                         project_to_edge(v->ebev->e, va, vb, midco);
1051                         for (k = 1; k < ns; k++) {
1052                                 get_point_on_round_edge(v->ebev, k, va, midco, vb, co);
1053                                 copy_v3_v3(mesh_vert(vm, i, 0, k)->co, co);
1054                                 if (!weld)
1055                                         create_mesh_bmvert(bm, vm, i, 0, k, bv->v);
1056                         }
1057                 }
1058                 v = v->next;
1059         } while (v != vm->boundstart);
1060
1061         if (weld) {
1062                 vm->mesh_kind = M_NONE;
1063                 for (k = 1; k < ns; k++) {
1064                         va = mesh_vert(vm, weld1->index, 0, k)->co;
1065                         vb = mesh_vert(vm, weld2->index, 0, ns - k)->co;
1066                         mid_v3_v3v3(co, va, vb);
1067                         copy_v3_v3(mesh_vert(vm, weld1->index, 0, k)->co, co);
1068                         create_mesh_bmvert(bm, vm, weld1->index, 0, k, bv->v);
1069                 }
1070                 for (k = 1; k < ns; k++)
1071                         copy_mesh_vert(vm, weld2->index, 0, ns - k, weld1->index, 0, k);
1072         }
1073
1074         if (vm->mesh_kind == M_ADJ)
1075                 bevel_build_rings(bm, bv);
1076         else if (vm->mesh_kind == M_POLY)
1077                 bevel_build_poly(bm, bv);
1078 }
1079
1080 /*
1081  * Construction around the vertex
1082  */
1083 static void bevel_vert_construct(BMesh *bm, BevelParams *bp, BMOperator *op, BMVert *v)
1084 {
1085
1086         BMOIter siter;
1087         BMEdge *bme;
1088         BevVert *bv;
1089         BMEdge *bme2, *unflagged_bme;
1090         BMFace *f;
1091         BMIter iter, iter2;
1092         EdgeHalf *e;
1093         int i, ntot, found_shared_face, ccw_test_sum;
1094         int nsel = 0;
1095
1096         /* Gather input selected edges.
1097          * Only bevel selected edges that have exactly two incident faces. */
1098         BMO_ITER (bme, &siter, bm, op, "geom", BM_EDGE) {
1099                 if ((bme->v1 == v) || (BM_edge_other_vert(bme, bme->v1) == v)) {
1100                         if (BM_edge_is_manifold(bme)) {
1101                                 BMO_elem_flag_enable(bm, bme, EDGE_SELECTED);
1102                                 nsel++;
1103                         }
1104                 }
1105         }
1106
1107         if (nsel == 0)
1108                 return;
1109
1110         ntot = BM_vert_edge_count(v);
1111         bv = (BevVert *)MEM_callocN(sizeof(BevVert), "BevVert");
1112         bv->v = v;
1113         bv->edgecount = ntot;
1114         bv->selcount = nsel;
1115         bv->edges = (EdgeHalf *)MEM_callocN(ntot * sizeof(EdgeHalf), "EdgeHalf");
1116         bv->vmesh = (VMesh *)MEM_callocN(sizeof(VMesh), "VMesh");
1117         bv->vmesh->seg = bp->seg;
1118         BLI_addtail(&bp->vertList, bv);
1119
1120         /* add edges to bv->edges in order that keeps adjacent edges sharing
1121          * a face, if possible */
1122         i = 0;
1123         bme = v->e;
1124         BMO_elem_flag_enable(bm, bme, BEVEL_FLAG);
1125         e = &bv->edges[0];
1126         e->e = bme;
1127         for (i = 0; i < ntot; i++) {
1128                 if (i > 0) {
1129                         /* find an unflagged edge bme2 that shares a face f with previous bme */
1130                         found_shared_face = 0;
1131                         unflagged_bme = NULL;
1132                         BM_ITER_ELEM (bme2, &iter, v, BM_EDGES_OF_VERT) {
1133                                 if (BMO_elem_flag_test(bm, bme2, BEVEL_FLAG))
1134                                         continue;
1135                                 if (!unflagged_bme)
1136                                         unflagged_bme = bme2;
1137                                 BM_ITER_ELEM (f, &iter2, bme2, BM_FACES_OF_EDGE) {
1138                                         if (BM_face_edge_share_loop(f, bme)) {
1139                                                 found_shared_face = 1;
1140                                                 break;
1141                                         }
1142                                 }
1143                                 if (found_shared_face)
1144                                         break;
1145                         }
1146                         e = &bv->edges[i];
1147                         if (found_shared_face) {
1148                                 e->e = bme2;
1149                                 e->fprev = f;
1150                                 bv->edges[i - 1].fnext = f;
1151                         }
1152                         else {
1153                                 e->e = unflagged_bme;
1154                         }
1155                 }
1156                 bme = e->e;
1157                 BMO_elem_flag_enable(bm, bme, BEVEL_FLAG);
1158                 if (BMO_elem_flag_test(bm, bme, EDGE_SELECTED)) {
1159                         e->isbev = 1;
1160                         e->seg = bp->seg;
1161                 }
1162                 else {
1163                         e->isbev = 0;
1164                         e->seg = 0;
1165                 }
1166                 e->isrev = (bme->v2 == v);
1167                 e->offset = e->isbev ? bp->offset : 0.0f;
1168         }
1169         /* find wrap-around shared face */
1170         BM_ITER_ELEM (f, &iter2, bme, BM_FACES_OF_EDGE) {
1171                 if (BM_face_edge_share_loop(f, bv->edges[0].e)) {
1172                         if (bv->edges[0].fnext == f)
1173                                 continue;   /* if two shared faces, want the other one now */
1174                         bv->edges[ntot - 1].fnext = f;
1175                         bv->edges[0].fprev = f;
1176                         break;
1177                 }
1178         }
1179
1180         /* remove BEVEL_FLAG now that we are finished with it*/
1181         for (i = 0; i < ntot; i++)
1182                 BMO_elem_flag_disable(bm, bv->edges[i].e, BEVEL_FLAG);
1183
1184         /* if edge array doesn't go CCW around vertex from average normal side,
1185          * reverse the array, being careful to reverse face pointers too */
1186         if (ntot > 1) {
1187                 ccw_test_sum = 0;
1188                 for (i = 0; i < ntot; i++)
1189                         ccw_test_sum += bev_ccw_test(bv->edges[i].e, bv->edges[(i + 1) % ntot].e,
1190                                                      bv->edges[i].fnext);
1191                 if (ccw_test_sum < 0) {
1192                         for (i = 0; i <= (ntot / 2) - 1; i++) {
1193                                 SWAP(EdgeHalf, bv->edges[i], bv->edges[ntot - i - 1]);
1194                                 SWAP(BMFace *, bv->edges[i].fprev, bv->edges[i].fnext);
1195                                 SWAP(BMFace *, bv->edges[ntot - i - 1].fprev, bv->edges[ntot - i - 1].fnext);
1196                         }
1197                         if (ntot % 2 == 1) {
1198                                 i = ntot / 2;
1199                                 SWAP(BMFace *, bv->edges[i].fprev,  bv->edges[i].fnext);
1200                         }
1201                 }
1202         }
1203
1204         for (i = 0; i < ntot; i++) {
1205                 e = &bv->edges[i];
1206                 e->next = &bv->edges[(i + 1) % ntot];
1207                 e->prev = &bv->edges[(i + ntot - 1) % ntot];
1208         }
1209
1210         build_boundary(bv);
1211         build_vmesh(bm, bv);
1212 }
1213
1214 /* Face f has at least one beveled vertex.  Rebuild f */
1215 static void rebuild_polygon(BMesh *bm, BevelParams *bp, BMFace *f)
1216 {
1217         BMIter liter;
1218         BMLoop *l, *lprev;
1219         BevVert *bv;
1220         BoundVert *v, *vstart, *vend;
1221         EdgeHalf *e, *eprev;
1222         VMesh *vm;
1223         int i, k;
1224         BMVert *bmv;
1225         BMVert **vv = NULL;
1226         BLI_array_declare(vv);
1227
1228         BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
1229                 bv = find_bevvert(bp, l->v);
1230                 if (bv) {
1231                         lprev = l->prev;
1232                         e = find_edge_half(bv, l->e);
1233                         eprev = find_edge_half(bv, lprev->e);
1234                         BLI_assert(e != NULL && eprev != NULL);
1235                         vstart = eprev->leftv;
1236                         if (e->isbev)
1237                                 vend = e->rightv;
1238                         else
1239                                 vend = e->leftv;
1240                         v = vstart;
1241                         vm = bv->vmesh;
1242                         BLI_array_append(vv, v->nv.v);
1243                         while (v != vend) {
1244                                 if (vm->mesh_kind == M_NONE && v->ebev && v->ebev->seg > 1 && v->ebev != e && v->ebev != eprev) {
1245                                         /* case of 3rd face opposite a beveled edge, with no vmesh */
1246                                         i = v->index;
1247                                         e = v->ebev;
1248                                         for (k = 1; k < e->seg; k++) {
1249                                                 bmv = mesh_vert(vm, i, 0, k)->v;
1250                                                 BLI_array_append(vv, bmv);
1251                                         }
1252                                 }
1253                                 v = v->prev;
1254                                 BLI_array_append(vv, v->nv.v);
1255                         }
1256                 }
1257                 else {
1258                         BLI_array_append(vv, l->v);
1259                 }
1260         }
1261         bev_create_ngon(bm, vv, BLI_array_count(vv), f);
1262         BLI_array_free(vv);
1263 }
1264
1265 /* All polygons touching v need rebuilding because beveling v has made new vertices */
1266 static void bevel_rebuild_existing_polygons(BMesh *bm, BevelParams *bp, BMVert *v)
1267 {
1268         void    *faces_stack[BM_DEFAULT_ITER_STACK_SIZE];
1269         int      faces_len, f_index;
1270         BMFace **faces = BM_iter_as_arrayN(bm, BM_FACES_OF_VERT, v, &faces_len,
1271                                            faces_stack, BM_DEFAULT_ITER_STACK_SIZE);
1272
1273         if (LIKELY(faces != NULL)) {
1274                 for (f_index = 0; f_index < faces_len; f_index++) {
1275                         BMFace *f = faces[f_index];
1276                         rebuild_polygon(bm, bp, f);
1277                         BM_face_kill(bm, f);
1278                 }
1279
1280                 if (faces != (BMFace **)faces_stack) {
1281                         MEM_freeN(faces);
1282                 }
1283         }
1284 }
1285
1286
1287
1288 /*
1289  * Build the polygons along the selected Edge
1290  */
1291 static void bevel_build_edge_polygons(BMesh *bm, BevelParams *bp, BMEdge *bme)
1292 {
1293         BevVert *bv1, *bv2;
1294         BMVert *bmv1, *bmv2, *bmv3, *bmv4, *bmv1i, *bmv2i, *bmv3i, *bmv4i;
1295         VMesh *vm1, *vm2;
1296         EdgeHalf *e1, *e2;
1297         BMFace *f1, *f2, *f;
1298         int k, nseg, i1, i2;
1299
1300         if (!BM_edge_is_manifold(bme))
1301                 return;
1302
1303         bv1 = find_bevvert(bp, bme->v1);
1304         bv2 = find_bevvert(bp, bme->v2);
1305
1306         BLI_assert(bv1 && bv2);
1307
1308         e1 = find_edge_half(bv1, bme);
1309         e2 = find_edge_half(bv2, bme);
1310
1311         BLI_assert(e1 && e2);
1312
1313         /*      v4                       v3
1314          *       \                      /
1315          *        e->v1 - e->v2
1316          *       /                      \
1317          *      v1                       v2 */
1318
1319         nseg = e1->seg;
1320         BLI_assert(nseg > 0 && nseg == e2->seg);
1321
1322         bmv1 = e1->leftv->nv.v;
1323         bmv4 = e1->rightv->nv.v;
1324         bmv2 = e2->rightv->nv.v;
1325         bmv3 = e2->leftv->nv.v;
1326
1327         BLI_assert(bmv1 && bmv2 && bmv3 && bmv4);
1328
1329         f1 = boundvert_rep_face(e1->leftv);
1330         f2 = boundvert_rep_face(e1->rightv);
1331
1332         if (nseg == 1) {
1333                 bev_create_quad_tri(bm, bmv1, bmv2, bmv3, bmv4, f1);
1334         }
1335         else {
1336                 i1 = e1->leftv->index;
1337                 i2 = e2->leftv->index;
1338                 vm1 = bv1->vmesh;
1339                 vm2 = bv2->vmesh;
1340                 bmv1i = bmv1;
1341                 bmv2i = bmv2;
1342                 for (k = 1; k <= nseg; k++) {
1343                         bmv4i = mesh_vert(vm1, i1, 0, k)->v;
1344                         bmv3i = mesh_vert(vm2, i2, 0, nseg - k)->v;
1345                         f = (k <= nseg / 2 + (nseg % 2)) ? f1 : f2;
1346                         bev_create_quad_tri(bm, bmv1i, bmv2i, bmv3i, bmv4i, f);
1347                         bmv1i = bmv4i;
1348                         bmv2i = bmv3i;
1349                 }
1350         }
1351 }
1352
1353
1354 static void free_bevel_params(BevelParams *bp)
1355 {
1356         BevVert *bv;
1357         VMesh *vm;
1358         BoundVert *v, *vnext;
1359
1360         for (bv = bp->vertList.first; bv; bv = bv->next) {
1361                 MEM_freeN(bv->edges);
1362                 vm = bv->vmesh;
1363                 v = vm->boundstart;
1364                 if (v) {
1365                         do {
1366                                 vnext = v->next;
1367                                 MEM_freeN(v);
1368                                 v = vnext;
1369                         } while (v != vm->boundstart);
1370                 }
1371                 if (vm->mesh)
1372                         MEM_freeN(vm->mesh);
1373                 MEM_freeN(vm);
1374         }
1375         BLI_freelistN(&bp->vertList);
1376 }
1377
1378 void bmo_bevel_exec(BMesh *bm, BMOperator *op)
1379 {
1380         BMOIter siter;
1381         BMVert *v;
1382         BMEdge *e;
1383         BevelParams bp;
1384
1385         bp.offset = BMO_slot_float_get(op, "offset");
1386         bp.op = op;
1387         bp.seg = BMO_slot_int_get(op, "segments");
1388
1389         if (bp.offset > 0) {
1390                 bp.vertList.first = bp.vertList.last = NULL;
1391
1392                 /* The analysis of the input vertices and execution additional constructions */
1393                 BMO_ITER (v, &siter, bm, op, "geom", BM_VERT) {
1394                         bevel_vert_construct(bm, &bp, op, v);
1395                 }
1396                 /* Build polygons for edges */
1397                 BMO_ITER (e, &siter, bm, op, "geom", BM_EDGE) {
1398                         bevel_build_edge_polygons(bm, &bp, e);
1399                 }
1400
1401                 BMO_ITER (v, &siter, bm, op, "geom", BM_VERT) {
1402                         bevel_rebuild_existing_polygons(bm, &bp, v);
1403                 }
1404
1405                 BMO_ITER (v, &siter, bm, op, "geom", BM_VERT) {
1406                         if (find_bevvert(&bp, v))
1407                                 BM_vert_kill(bm, v);
1408                 }
1409                 free_bevel_params(&bp);
1410         }
1411
1412 }
1413
1414 #else
1415 #define BEVEL_FLAG  1
1416 #define BEVEL_DEL   2
1417 #define FACE_NEW    4
1418 #define EDGE_OLD    8
1419 #define FACE_OLD    16
1420 #define VERT_OLD    32
1421 #define FACE_SPAN   64
1422 #define FACE_HOLE   128
1423
1424 typedef struct LoopTag {
1425         BMVert *newv;
1426 } LoopTag;
1427
1428 typedef struct EdgeTag {
1429         BMVert *newv1, *newv2;
1430 } EdgeTag;
1431
1432 static void calc_corner_co(BMLoop *l, const float fac, float r_co[3],
1433                            const short do_dist, const short do_even)
1434 {
1435         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];
1436         int is_concave;
1437
1438         /* first get the prev/next verts */
1439         if (l->f->len > 2) {
1440                 copy_v3_v3(l_co_prev, l->prev->v->co);
1441                 copy_v3_v3(l_co, l->v->co);
1442                 copy_v3_v3(l_co_next, l->next->v->co);
1443
1444                 /* calculate normal */
1445                 sub_v3_v3v3(l_vec_prev, l_co_prev, l_co);
1446                 sub_v3_v3v3(l_vec_next, l_co_next, l_co);
1447
1448                 cross_v3_v3v3(no, l_vec_prev, l_vec_next);
1449                 is_concave = dot_v3v3(no, l->f->no) > 0.0f;
1450         }
1451         else {
1452                 BMIter iter;
1453                 BMLoop *l2;
1454                 float up[3] = {0.0f, 0.0f, 1.0f};
1455
1456                 copy_v3_v3(l_co_prev, l->prev->v->co);
1457                 copy_v3_v3(l_co, l->v->co);
1458                 
1459                 BM_ITER_ELEM (l2, &iter, l->v, BM_LOOPS_OF_VERT) {
1460                         if (l2->f != l->f) {
1461                                 copy_v3_v3(l_co_next, BM_edge_other_vert(l2->e, l2->next->v)->co);
1462                                 break;
1463                         }
1464                 }
1465                 
1466                 sub_v3_v3v3(l_vec_prev, l_co_prev, l_co);
1467                 sub_v3_v3v3(l_vec_next, l_co_next, l_co);
1468
1469                 cross_v3_v3v3(no, l_vec_prev, l_vec_next);
1470                 if (dot_v3v3(no, no) == 0.0f) {
1471                         no[0] = no[1] = 0.0f; no[2] = -1.0f;
1472                 }
1473                 
1474                 is_concave = dot_v3v3(no, up) < 0.0f;
1475         }
1476
1477
1478         /* now calculate the new location */
1479         if (do_dist) { /* treat 'fac' as distance */
1480
1481                 normalize_v3(l_vec_prev);
1482                 normalize_v3(l_vec_next);
1483
1484                 add_v3_v3v3(co_ofs, l_vec_prev, l_vec_next);
1485                 if (UNLIKELY(normalize_v3(co_ofs) == 0.0f)) {  /* edges form a straight line */
1486                         cross_v3_v3v3(co_ofs, l_vec_prev, l->f->no);
1487                 }
1488
1489                 if (do_even) {
1490                         negate_v3(l_vec_next);
1491                         mul_v3_fl(co_ofs, fac * shell_angle_to_dist(0.5f * angle_normalized_v3v3(l_vec_prev, l_vec_next)));
1492                         /* negate_v3(l_vec_next); */ /* no need unless we use again */
1493                 }
1494                 else {
1495                         mul_v3_fl(co_ofs, fac);
1496                 }
1497         }
1498         else { /* treat as 'fac' as a factor (0 - 1) */
1499
1500                 /* not strictly necessary, balance vectors
1501                  * so the longer edge doesn't skew the result,
1502                  * gives nicer, move even output.
1503                  *
1504                  * Use the minimum rather then the middle value so skinny faces don't flip along the short axis */
1505                 float min_fac = min_ff(normalize_v3(l_vec_prev), normalize_v3(l_vec_next));
1506                 float angle;
1507
1508                 if (do_even) {
1509                         negate_v3(l_vec_next);
1510                         angle = angle_normalized_v3v3(l_vec_prev, l_vec_next);
1511                         negate_v3(l_vec_next); /* no need unless we use again */
1512                 }
1513                 else {
1514                         angle = 0.0f;
1515                 }
1516
1517                 mul_v3_fl(l_vec_prev, min_fac);
1518                 mul_v3_fl(l_vec_next, min_fac);
1519
1520                 add_v3_v3v3(co_ofs, l_vec_prev, l_vec_next);
1521
1522                 if (UNLIKELY(is_zero_v3(co_ofs))) {
1523                         cross_v3_v3v3(co_ofs, l_vec_prev, l->f->no);
1524                         normalize_v3(co_ofs);
1525                         mul_v3_fl(co_ofs, min_fac);
1526                 }
1527
1528                 /* done */
1529                 if (do_even) {
1530                         mul_v3_fl(co_ofs, (fac * 0.5f) * shell_angle_to_dist(0.5f * angle));
1531                 }
1532                 else {
1533                         mul_v3_fl(co_ofs, fac * 0.5f);
1534                 }
1535         }
1536
1537         /* apply delta vec */
1538         if (is_concave)
1539                 negate_v3(co_ofs);
1540
1541         add_v3_v3v3(r_co, co_ofs, l->v->co);
1542 }
1543
1544
1545 #define ETAG_SET(e, v, nv)  (                                                 \
1546         (v) == (e)->v1 ?                                                          \
1547                 (etags[BM_elem_index_get((e))].newv1 = (nv)) :                        \
1548                 (etags[BM_elem_index_get((e))].newv2 = (nv))                          \
1549         )
1550
1551 #define ETAG_GET(e, v)  (                                                     \
1552         (v) == (e)->v1 ?                                                          \
1553                 (etags[BM_elem_index_get((e))].newv1) :                               \
1554                 (etags[BM_elem_index_get((e))].newv2)                                 \
1555         )
1556
1557 void bmo_bevel_exec(BMesh *bm, BMOperator *op)
1558 {
1559         BMOIter siter;
1560         BMIter iter;
1561         BMEdge *e;
1562         BMVert *v;
1563         BMFace **faces = NULL, *f;
1564         LoopTag *tags = NULL, *tag;
1565         EdgeTag *etags = NULL;
1566         BMVert **verts = NULL;
1567         BMEdge **edges = NULL;
1568         BLI_array_declare(faces);
1569         BLI_array_declare(tags);
1570         BLI_array_declare(etags);
1571         BLI_array_declare(verts);
1572         BLI_array_declare(edges);
1573         SmallHash hash;
1574         float fac = BMO_slot_float_get(op, "percent");
1575         const short do_even = BMO_slot_bool_get(op, "use_even");
1576         const short do_dist = BMO_slot_bool_get(op, "use_dist");
1577         int i, li, has_elens, HasMDisps = CustomData_has_layer(&bm->ldata, CD_MDISPS);
1578         
1579         has_elens = CustomData_has_layer(&bm->edata, CD_PROP_FLT) && BMO_slot_bool_get(op, "use_lengths");
1580         if (has_elens) {
1581                 li = BMO_slot_int_get(op, "lengthlayer");
1582         }
1583         
1584         BLI_smallhash_init(&hash);
1585         
1586         BMO_ITER (e, &siter, bm, op, "geom", BM_EDGE) {
1587                 BMO_elem_flag_enable(bm, e, BEVEL_FLAG | BEVEL_DEL);
1588                 BMO_elem_flag_enable(bm, e->v1, BEVEL_FLAG | BEVEL_DEL);
1589                 BMO_elem_flag_enable(bm, e->v2, BEVEL_FLAG | BEVEL_DEL);
1590                 
1591                 if (BM_edge_face_count(e) < 2) {
1592                         BMO_elem_flag_disable(bm, e, BEVEL_DEL);
1593                         BMO_elem_flag_disable(bm, e->v1, BEVEL_DEL);
1594                         BMO_elem_flag_disable(bm, e->v2, BEVEL_DEL);
1595                 }
1596 #if 0
1597                 if (BM_edge_is_wire(e)) {
1598                         BMVert *verts[2] = {e->v1, e->v2};
1599                         BMEdge *edges[2] = {e, BM_edge_create(bm, e->v1, e->v2, e, 0)};
1600                         
1601                         BMO_elem_flag_enable(bm, edges[1], BEVEL_FLAG);
1602                         BM_face_create(bm, verts, edges, 2, FALSE);
1603                 }
1604 #endif
1605         }
1606         
1607         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
1608                 BMO_elem_flag_enable(bm, v, VERT_OLD);
1609         }
1610
1611 #if 0
1612         /* a bit of cleaner code that, alas, doens't work. */
1613         /* build edge tag */
1614         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
1615                 if (BMO_elem_flag_test(bm, e->v1, BEVEL_FLAG) || BMO_elem_flag_test(bm, e->v2, BEVEL_FLAG)) {
1616                         BMIter liter;
1617                         BMLoop *l;
1618                         
1619                         if (!BMO_elem_flag_test(bm, e, EDGE_OLD)) {
1620                                 BM_elem_index_set(e, BLI_array_count(etags)); /* set_dirty! */
1621                                 BLI_array_grow_one(etags);
1622                                 
1623                                 BMO_elem_flag_enable(bm, e, EDGE_OLD);
1624                         }
1625                         
1626                         BM_ITER_ELEM (l, &liter, e, BM_LOOPS_OF_EDGE) {
1627                                 BMLoop *l2;
1628                                 BMIter liter2;
1629                                 
1630                                 if (BMO_elem_flag_test(bm, l->f, BEVEL_FLAG))
1631                                         continue;
1632
1633                                 BM_ITER_ELEM (l2, &liter2, l->f, BM_LOOPS_OF_FACE) {
1634                                         BM_elem_index_set(l2, BLI_array_count(tags)); /* set_loop */
1635                                         BLI_array_grow_one(tags);
1636
1637                                         if (!BMO_elem_flag_test(bm, l2->e, EDGE_OLD)) {
1638                                                 BM_elem_index_set(l2->e, BLI_array_count(etags)); /* set_dirty! */
1639                                                 BLI_array_grow_one(etags);
1640                                                 
1641                                                 BMO_elem_flag_enable(bm, l2->e, EDGE_OLD);
1642                                         }
1643                                 }
1644
1645                                 BMO_elem_flag_enable(bm, l->f, BEVEL_FLAG);
1646                                 BLI_array_append(faces, l->f);
1647                         }
1648                 }
1649                 else {
1650                         BM_elem_index_set(e, -1); /* set_dirty! */
1651                 }
1652         }
1653 #endif
1654         
1655         /* create and assign looptag structure */
1656         BMO_ITER (e, &siter, bm, op, "geom", BM_EDGE) {
1657                 BMLoop *l;
1658                 BMIter liter;
1659
1660                 BMO_elem_flag_enable(bm, e->v1, BEVEL_FLAG | BEVEL_DEL);
1661                 BMO_elem_flag_enable(bm, e->v2, BEVEL_FLAG | BEVEL_DEL);
1662                 
1663                 if (BM_edge_face_count(e) < 2) {
1664                         BMO_elem_flag_disable(bm, e, BEVEL_DEL);
1665                         BMO_elem_flag_disable(bm, e->v1, BEVEL_DEL);
1666                         BMO_elem_flag_disable(bm, e->v2, BEVEL_DEL);
1667                 }
1668                 
1669                 if (!BLI_smallhash_haskey(&hash, (intptr_t)e)) {
1670                         BLI_array_grow_one(etags);
1671                         BM_elem_index_set(e, BLI_array_count(etags) - 1); /* set_dirty! */
1672                         BLI_smallhash_insert(&hash, (intptr_t)e, NULL);
1673                         BMO_elem_flag_enable(bm, e, EDGE_OLD);
1674                 }
1675                 
1676                 /* find all faces surrounding e->v1 and, e->v2 */
1677                 for (i = 0; i < 2; i++) {
1678                         BM_ITER_ELEM (l, &liter, i ? e->v2 : e->v1, BM_LOOPS_OF_VERT) {
1679                                 BMLoop *l2;
1680                                 BMIter liter2;
1681                                 
1682                                 /* see if we've already processed this loop's fac */
1683                                 if (BLI_smallhash_haskey(&hash, (intptr_t)l->f))
1684                                         continue;
1685                                 
1686                                 /* create tags for all loops in l-> */
1687                                 BM_ITER_ELEM (l2, &liter2, l->f, BM_LOOPS_OF_FACE) {
1688                                         BLI_array_grow_one(tags);
1689                                         BM_elem_index_set(l2, BLI_array_count(tags) - 1); /* set_loop */
1690                                         
1691                                         if (!BLI_smallhash_haskey(&hash, (intptr_t)l2->e)) {
1692                                                 BLI_array_grow_one(etags);
1693                                                 BM_elem_index_set(l2->e, BLI_array_count(etags) - 1); /* set_dirty! */
1694                                                 BLI_smallhash_insert(&hash, (intptr_t)l2->e, NULL);
1695                                                 BMO_elem_flag_enable(bm, l2->e, EDGE_OLD);
1696                                         }
1697                                 }
1698
1699                                 BLI_smallhash_insert(&hash, (intptr_t)l->f, NULL);
1700                                 BMO_elem_flag_enable(bm, l->f, BEVEL_FLAG);
1701                                 BLI_array_append(faces, l->f);
1702                         }
1703                 }
1704         }
1705
1706         bm->elem_index_dirty |= BM_EDGE;
1707         
1708         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
1709                 BMIter eiter;
1710                 
1711                 if (!BMO_elem_flag_test(bm, v, BEVEL_FLAG))
1712                         continue;
1713                 
1714                 BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
1715                         if (!BMO_elem_flag_test(bm, e, BEVEL_FLAG) && !ETAG_GET(e, v)) {
1716                                 BMVert *v2;
1717                                 float co[3];
1718                                 
1719                                 v2 = BM_edge_other_vert(e, v);
1720                                 sub_v3_v3v3(co, v2->co, v->co);
1721                                 if (has_elens) {
1722                                         float elen = *(float *)CustomData_bmesh_get_n(&bm->edata, e->head.data, CD_PROP_FLT, li);
1723
1724                                         normalize_v3(co);
1725                                         mul_v3_fl(co, elen);
1726                                 }
1727                                 
1728                                 mul_v3_fl(co, fac);
1729                                 add_v3_v3(co, v->co);
1730                                 
1731                                 v2 = BM_vert_create(bm, co, v);
1732                                 ETAG_SET(e, v, v2);
1733                         }
1734                 }
1735         }
1736         
1737         for (i = 0; i < BLI_array_count(faces); i++) {
1738                 BMLoop *l;
1739                 BMIter liter;
1740                 
1741                 BMO_elem_flag_enable(bm, faces[i], FACE_OLD);
1742                 
1743                 BM_ITER_ELEM (l, &liter, faces[i], BM_LOOPS_OF_FACE) {
1744                         float co[3];
1745
1746                         if (BMO_elem_flag_test(bm, l->e, BEVEL_FLAG)) {
1747                                 if (BMO_elem_flag_test(bm, l->prev->e, BEVEL_FLAG)) {
1748                                         tag = tags + BM_elem_index_get(l);
1749                                         calc_corner_co(l, fac, co, do_dist, do_even);
1750                                         tag->newv = BM_vert_create(bm, co, l->v);
1751                                 }
1752                                 else {
1753                                         tag = tags + BM_elem_index_get(l);
1754                                         tag->newv = ETAG_GET(l->prev->e, l->v);
1755                                         
1756                                         if (!tag->newv) {
1757                                                 sub_v3_v3v3(co, l->prev->v->co, l->v->co);
1758                                                 if (has_elens) {
1759                                                         float elen = *(float *)CustomData_bmesh_get_n(&bm->edata, l->prev->e->head.data,
1760                                                                                                       CD_PROP_FLT, li);
1761
1762                                                         normalize_v3(co);
1763                                                         mul_v3_fl(co, elen);
1764                                                 }
1765
1766                                                 mul_v3_fl(co, fac);
1767                                                 add_v3_v3(co, l->v->co);
1768
1769                                                 tag->newv = BM_vert_create(bm, co, l->v);
1770                                                 
1771                                                 ETAG_SET(l->prev->e, l->v, tag->newv);
1772                                         }
1773                                 }
1774                         }
1775                         else if (BMO_elem_flag_test(bm, l->v, BEVEL_FLAG)) {
1776                                 tag = tags + BM_elem_index_get(l);
1777                                 tag->newv = ETAG_GET(l->e, l->v);
1778
1779                                 if (!tag->newv) {
1780                                         sub_v3_v3v3(co, l->next->v->co, l->v->co);
1781                                         if (has_elens) {
1782                                                 float elen = *(float *)CustomData_bmesh_get_n(&bm->edata, l->e->head.data, CD_PROP_FLT, li);
1783
1784                                                 normalize_v3(co);
1785                                                 mul_v3_fl(co, elen);
1786                                         }
1787                                         
1788                                         mul_v3_fl(co, fac);
1789                                         add_v3_v3(co, l->v->co);
1790
1791                                         tag = tags + BM_elem_index_get(l);
1792                                         tag->newv = BM_vert_create(bm, co, l->v);
1793                                         
1794                                         ETAG_SET(l->e, l->v, tag->newv);
1795                                 }
1796                         }
1797                         else {
1798                                 tag = tags + BM_elem_index_get(l);
1799                                 tag->newv = l->v;
1800                                 BMO_elem_flag_disable(bm, l->v, BEVEL_DEL);
1801                         }
1802                 }
1803         }
1804         
1805         /* create new faces inset from original face */
1806         for (i = 0; i < BLI_array_count(faces); i++) {
1807                 BMLoop *l;
1808                 BMIter liter;
1809                 BMFace *f;
1810                 BMVert *lastv = NULL, *firstv = NULL;
1811
1812                 BMO_elem_flag_enable(bm, faces[i], BEVEL_DEL);
1813                 
1814                 BLI_array_empty(verts);
1815                 BLI_array_empty(edges);
1816                 
1817                 BM_ITER_ELEM (l, &liter, faces[i], BM_LOOPS_OF_FACE) {
1818                         BMVert *v2;
1819                         
1820                         tag = tags + BM_elem_index_get(l);
1821                         BLI_array_append(verts, tag->newv);
1822                         
1823                         if (!firstv)
1824                                 firstv = tag->newv;
1825                         
1826                         if (lastv) {
1827                                 e = BM_edge_create(bm, lastv, tag->newv, l->e, TRUE);
1828                                 BM_elem_attrs_copy(bm, bm, l->prev->e, e);
1829                                 BLI_array_append(edges, e);
1830                         }
1831                         lastv = tag->newv;
1832                         
1833                         v2 = ETAG_GET(l->e, l->next->v);
1834                         
1835                         tag = &tags[BM_elem_index_get(l->next)];
1836                         if (!BMO_elem_flag_test(bm, l->e, BEVEL_FLAG) && v2 && v2 != tag->newv) {
1837                                 BLI_array_append(verts, v2);
1838                                 
1839                                 e = BM_edge_create(bm, lastv, v2, l->e, TRUE);
1840                                 BM_elem_attrs_copy(bm, bm, l->e, e);
1841                                 
1842                                 BLI_array_append(edges, e);
1843                                 lastv = v2;
1844                         }
1845                 }
1846                 
1847                 e = BM_edge_create(bm, firstv, lastv, BM_FACE_FIRST_LOOP(faces[i])->e, TRUE);
1848                 if (BM_FACE_FIRST_LOOP(faces[i])->prev->e != e) {
1849                         BM_elem_attrs_copy(bm, bm, BM_FACE_FIRST_LOOP(faces[i])->prev->e, e);
1850                 }
1851                 BLI_array_append(edges, e);
1852                 
1853                 f = BM_face_create_ngon(bm, verts[0], verts[1], edges, BLI_array_count(edges), FALSE);
1854                 if (UNLIKELY(f == NULL)) {
1855                         printf("%s: could not make face!\n", __func__);
1856                         continue;
1857                 }
1858
1859                 BMO_elem_flag_enable(bm, f, FACE_NEW);
1860         }
1861
1862         for (i = 0; i < BLI_array_count(faces); i++) {
1863                 BMLoop *l;
1864                 BMIter liter;
1865                 int j;
1866                 
1867                 /* create quad spans between split edge */
1868                 BM_ITER_ELEM (l, &liter, faces[i], BM_LOOPS_OF_FACE) {
1869                         BMVert *v1 = NULL, *v2 = NULL, *v3 = NULL, *v4 = NULL;
1870                         
1871                         if (!BMO_elem_flag_test(bm, l->e, BEVEL_FLAG))
1872                                 continue;
1873                         
1874                         v1 = tags[BM_elem_index_get(l)].newv;
1875                         v2 = tags[BM_elem_index_get(l->next)].newv;
1876                         if (l->radial_next != l) {
1877                                 v3 = tags[BM_elem_index_get(l->radial_next)].newv;
1878                                 if (l->radial_next->next->v == l->next->v) {
1879                                         v4 = v3;
1880                                         v3 = tags[BM_elem_index_get(l->radial_next->next)].newv;
1881                                 }
1882                                 else {
1883                                         v4 = tags[BM_elem_index_get(l->radial_next->next)].newv;
1884                                 }
1885                         }
1886                         else {
1887                                 /* the loop is on a boundar */
1888                                 v3 = l->next->v;
1889                                 v4 = l->v;
1890                                 
1891                                 for (j = 0; j < 2; j++) {
1892                                         BMIter eiter;
1893                                         BMVert *v = j ? v4 : v3;
1894
1895                                         BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
1896                                                 if (!BM_vert_in_edge(e, v3) || !BM_vert_in_edge(e, v4))
1897                                                         continue;
1898                                                 
1899                                                 if (!BMO_elem_flag_test(bm, e, BEVEL_FLAG) && BMO_elem_flag_test(bm, e, EDGE_OLD)) {
1900                                                         BMVert *vv;
1901                                                         
1902                                                         vv = ETAG_GET(e, v);
1903                                                         if (!vv || BMO_elem_flag_test(bm, vv, BEVEL_FLAG))
1904                                                                 continue;
1905                                                         
1906                                                         if (j) {
1907                                                                 v1 = vv;
1908                                                         }
1909                                                         else {
1910                                                                 v2 = vv;
1911                                                         }
1912                                                         break;
1913                                                 }
1914                                         }
1915                                 }
1916
1917                                 BMO_elem_flag_disable(bm, v3, BEVEL_DEL);
1918                                 BMO_elem_flag_disable(bm, v4, BEVEL_DEL);
1919                         }
1920                         
1921                         if (v1 != v2 && v2 != v3 && v3 != v4) {
1922                                 BMIter liter2;
1923                                 BMLoop *l2, *l3;
1924                                 BMEdge *e1, *e2;
1925                                 float d1, d2, *d3;
1926                                 
1927                                 f = BM_face_create_quad_tri(bm, v4, v3, v2, v1, l->f, TRUE);
1928
1929                                 e1 = BM_edge_exists(v4, v3);
1930                                 e2 = BM_edge_exists(v2, v1);
1931                                 BM_elem_attrs_copy(bm, bm, l->e, e1);
1932                                 BM_elem_attrs_copy(bm, bm, l->e, e2);
1933                                 
1934                                 /* set edge lengths of cross edges as the average of the cross edges they're based o */
1935                                 if (has_elens) {
1936                                         /* angle happens not to be used. why? - not sure it just isn't - campbell.
1937                                          * leave this in in case we need to use it later */
1938 #if 0
1939                                         float ang;
1940 #endif
1941                                         e1 = BM_edge_exists(v1, v4);
1942                                         e2 = BM_edge_exists(v2, v3);
1943                                         
1944                                         if (l->radial_next->v == l->v) {
1945                                                 l2 = l->radial_next->prev;
1946                                                 l3 = l->radial_next->next;
1947                                         }
1948                                         else {
1949                                                 l2 = l->radial_next->next;
1950                                                 l3 = l->radial_next->prev;
1951                                         }
1952                                         
1953                                         d3 = CustomData_bmesh_get_n(&bm->edata, e1->head.data, CD_PROP_FLT, li);
1954                                         d1 = *(float *)CustomData_bmesh_get_n(&bm->edata, l->prev->e->head.data, CD_PROP_FLT, li);
1955                                         d2 = *(float *)CustomData_bmesh_get_n(&bm->edata, l2->e->head.data, CD_PROP_FLT, li);
1956 #if 0
1957                                         ang = angle_v3v3v3(l->prev->v->co, l->v->co, BM_edge_other_vert(l2->e, l->v)->co);
1958 #endif
1959                                         *d3 = (d1 + d2) * 0.5f;
1960                                         
1961                                         d3 = CustomData_bmesh_get_n(&bm->edata, e2->head.data, CD_PROP_FLT, li);
1962                                         d1 = *(float *)CustomData_bmesh_get_n(&bm->edata, l->next->e->head.data, CD_PROP_FLT, li);
1963                                         d2 = *(float *)CustomData_bmesh_get_n(&bm->edata, l3->e->head.data, CD_PROP_FLT, li);
1964 #if 0
1965                                         ang = angle_v3v3v3(BM_edge_other_vert(l->next->e, l->next->v)->co, l->next->v->co,
1966                                                            BM_edge_other_vert(l3->e, l->next->v)->co);
1967 #endif
1968                                         *d3 = (d1 + d2) * 0.5f;
1969                                 }
1970
1971                                 if (UNLIKELY(f == NULL)) {
1972                                         fprintf(stderr, "%s: face index out of range! (bmesh internal error)\n", __func__);
1973                                         continue;
1974                                 }
1975                                 
1976                                 BMO_elem_flag_enable(bm, f, FACE_NEW | FACE_SPAN);
1977                                 
1978                                 /* un-tag edges in f for deletio */
1979                                 BM_ITER_ELEM (l2, &liter2, f, BM_LOOPS_OF_FACE) {
1980                                         BMO_elem_flag_disable(bm, l2->e, BEVEL_DEL);
1981                                 }
1982                         }
1983                         else {
1984                                 f = NULL;
1985                         }
1986                 }
1987         }
1988         
1989         /* fill in holes at vertices */
1990         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
1991                 BMIter eiter;
1992                 BMVert *vv, *vstart = NULL, *lastv = NULL;
1993                 SmallHash tmphash;
1994                 int rad, insorig = 0, err = 0;
1995
1996                 BLI_smallhash_init(&tmphash);
1997
1998                 if (!BMO_elem_flag_test(bm, v, BEVEL_FLAG))
1999                         continue;
2000                 
2001                 BLI_array_empty(verts);
2002                 BLI_array_empty(edges);
2003                 
2004                 BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
2005                         BMIter liter;
2006                         BMVert *v1 = NULL, *v2 = NULL;
2007                         BMLoop *l;
2008                         
2009                         if (BM_edge_face_count(e) < 2)
2010                                 insorig = 1;
2011                         
2012                         if (BM_elem_index_get(e) == -1)
2013                                 continue;
2014                         
2015                         rad = 0;
2016                         BM_ITER_ELEM (l, &liter, e, BM_LOOPS_OF_EDGE) {
2017                                 if (!BMO_elem_flag_test(bm, l->f, FACE_OLD))
2018                                         continue;
2019                                 
2020                                 rad++;
2021                                 
2022                                 tag = tags + BM_elem_index_get((l->v == v) ? l : l->next);
2023                                 
2024                                 if (!v1)
2025                                         v1 = tag->newv;
2026                                 else if (!v2)
2027                                         v2 = tag->newv;
2028                         }
2029                         
2030                         if (rad < 2)
2031                                 insorig = 1;
2032                         
2033                         if (!v1)
2034                                 v1 = ETAG_GET(e, v);
2035                         if (!v2 || v1 == v2)
2036                                 v2 = ETAG_GET(e, v);
2037                         
2038                         if (v1) {
2039                                 if (!BLI_smallhash_haskey(&tmphash, (intptr_t)v1)) {
2040                                         BLI_array_append(verts, v1);
2041                                         BLI_smallhash_insert(&tmphash, (intptr_t)v1, NULL);
2042                                 }
2043                                 
2044                                 if (v2 && v1 != v2 && !BLI_smallhash_haskey(&tmphash, (intptr_t)v2)) {
2045                                         BLI_array_append(verts, v2);
2046                                         BLI_smallhash_insert(&tmphash, (intptr_t)v2, NULL);
2047                                 }
2048                         }
2049                 }
2050                 
2051                 if (!BLI_array_count(verts))
2052                         continue;
2053                 
2054                 if (insorig) {
2055                         BLI_array_append(verts, v);
2056                         BLI_smallhash_insert(&tmphash, (intptr_t)v, NULL);
2057                 }
2058                 
2059                 /* find edges that exist between vertices in verts.  this is basically
2060                  * a topological walk of the edges connecting them */
2061                 vstart = vstart ? vstart : verts[0];
2062                 vv = vstart;
2063                 do {
2064                         BM_ITER_ELEM (e, &eiter, vv, BM_EDGES_OF_VERT) {
2065                                 BMVert *vv2 = BM_edge_other_vert(e, vv);
2066                                 
2067                                 if (vv2 != lastv && BLI_smallhash_haskey(&tmphash, (intptr_t)vv2)) {
2068                                         /* if we've go over the same vert twice, break out of outer loop */
2069                                         if (BLI_smallhash_lookup(&tmphash, (intptr_t)vv2) != NULL) {
2070                                                 e = NULL;
2071                                                 err = 1;
2072                                                 break;
2073                                         }
2074                                         
2075                                         /* use self pointer as ta */
2076                                         BLI_smallhash_remove(&tmphash, (intptr_t)vv2);
2077                                         BLI_smallhash_insert(&tmphash, (intptr_t)vv2, vv2);
2078                                         
2079                                         lastv = vv;
2080                                         BLI_array_append(edges, e);
2081                                         vv = vv2;
2082                                         break;
2083                                 }
2084                         }
2085
2086                         if (e == NULL) {
2087                                 break;
2088                         }
2089                 } while (vv != vstart);
2090                 
2091                 if (err) {
2092                         continue;
2093                 }
2094
2095                 /* there may not be a complete loop of edges, so start again and make
2096                  * final edge afterwards.  in this case, the previous loop worked to
2097                  * find one of the two edges at the extremes. */
2098                 if (vv != vstart) {
2099                         /* undo previous taggin */
2100                         for (i = 0; i < BLI_array_count(verts); i++) {
2101                                 BLI_smallhash_remove(&tmphash, (intptr_t)verts[i]);
2102                                 BLI_smallhash_insert(&tmphash, (intptr_t)verts[i], NULL);
2103                         }
2104
2105                         vstart = vv;
2106                         lastv = NULL;
2107                         BLI_array_empty(edges);
2108                         do {
2109                                 BM_ITER_ELEM (e, &eiter, vv, BM_EDGES_OF_VERT) {
2110                                         BMVert *vv2 = BM_edge_other_vert(e, vv);
2111                                         
2112                                         if (vv2 != lastv && BLI_smallhash_haskey(&tmphash, (intptr_t)vv2)) {
2113                                                 /* if we've go over the same vert twice, break out of outer loo */
2114                                                 if (BLI_smallhash_lookup(&tmphash, (intptr_t)vv2) != NULL) {
2115                                                         e = NULL;
2116                                                         err = 1;
2117                                                         break;
2118                                                 }
2119                                                 
2120                                                 /* use self pointer as ta */
2121                                                 BLI_smallhash_remove(&tmphash, (intptr_t)vv2);
2122                                                 BLI_smallhash_insert(&tmphash, (intptr_t)vv2, vv2);
2123                                                 
2124                                                 lastv = vv;
2125                                                 BLI_array_append(edges, e);
2126                                                 vv = vv2;
2127                                                 break;
2128                                         }
2129                                 }
2130                                 if (e == NULL)
2131                                         break;
2132                         } while (vv != vstart);
2133                         
2134                         if (!err) {
2135                                 e = BM_edge_create(bm, vv, vstart, NULL, TRUE);
2136                                 BLI_array_append(edges, e);
2137                         }
2138                 }
2139                 
2140                 if (err)
2141                         continue;
2142                 
2143                 if (BLI_array_count(edges) >= 3) {
2144                         BMFace *f;
2145                         
2146                         if (BM_face_exists(bm, verts, BLI_array_count(verts), &f))
2147                                 continue;
2148                         
2149                         f = BM_face_create_ngon(bm, lastv, vstart, edges, BLI_array_count(edges), FALSE);
2150                         if (UNLIKELY(f == NULL)) {
2151                                 fprintf(stderr, "%s: in bevel vert fill! (bmesh internal error)\n", __func__);
2152                         }
2153                         else {
2154                                 BMO_elem_flag_enable(bm, f, FACE_NEW | FACE_HOLE);
2155                         }
2156                 }
2157                 BLI_smallhash_release(&tmphash);
2158         }
2159         
2160         /* copy over customdat */
2161         for (i = 0; i < BLI_array_count(faces); i++) {
2162                 BMLoop *l;
2163                 BMIter liter;
2164                 BMFace *f = faces[i];
2165                 
2166                 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
2167                         BMLoop *l2;
2168                         BMIter liter2;
2169                         
2170                         tag = tags + BM_elem_index_get(l);
2171                         if (!tag->newv)
2172                                 continue;
2173                         
2174                         BM_ITER_ELEM (l2, &liter2, tag->newv, BM_LOOPS_OF_VERT) {
2175                                 if (!BMO_elem_flag_test(bm, l2->f, FACE_NEW) || (l2->v != tag->newv && l2->v != l->v))
2176                                         continue;
2177                                 
2178                                 if (tag->newv != l->v || HasMDisps) {
2179                                         BM_elem_attrs_copy(bm, bm, l->f, l2->f);
2180                                         BM_loop_interp_from_face(bm, l2, l->f, TRUE, TRUE);
2181                                 }
2182                                 else {
2183                                         BM_elem_attrs_copy(bm, bm, l->f, l2->f);
2184                                         BM_elem_attrs_copy(bm, bm, l, l2);
2185                                 }
2186                                 
2187                                 if (HasMDisps) {
2188                                         BMLoop *l3;
2189                                         BMIter liter3;
2190                                         
2191                                         BM_ITER_ELEM (l3, &liter3, l2->f, BM_LOOPS_OF_FACE) {
2192                                                 BM_loop_interp_multires(bm, l3, l->f);
2193                                         }
2194                                 }
2195                         }
2196                 }
2197         }
2198         
2199         /* handle vertices along boundary edge */
2200         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
2201                 if (BMO_elem_flag_test(bm, v, VERT_OLD) &&
2202                     BMO_elem_flag_test(bm, v, BEVEL_FLAG) &&
2203                     !BMO_elem_flag_test(bm, v, BEVEL_DEL))
2204                 {
2205                         BMLoop *l;
2206                         BMLoop *lorig = NULL;
2207                         BMIter liter;
2208                         
2209                         BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
2210                                 // BMIter liter2;
2211                                 // BMLoop *l2 = l->v == v ? l : l->next, *l3;
2212                                 
2213                                 if (BMO_elem_flag_test(bm, l->f, FACE_OLD)) {
2214                                         lorig = l;
2215                                         break;
2216                                 }
2217                         }
2218                         
2219                         if (!lorig)
2220                                 continue;
2221                         
2222                         BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
2223                                 BMLoop *l2 = l->v == v ? l : l->next;
2224                                 
2225                                 BM_elem_attrs_copy(bm, bm, lorig->f, l2->f);
2226                                 BM_elem_attrs_copy(bm, bm, lorig, l2);
2227                         }
2228                 }
2229         }
2230 #if 0
2231         /* clean up any remaining 2-edged face */
2232         BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
2233                 if (f->len == 2) {
2234                         BMFace *faces[2] = {f, BM_FACE_FIRST_LOOP(f)->radial_next->f};
2235                         
2236                         if (faces[0] == faces[1])
2237                                 BM_face_kill(bm, f);
2238                         else
2239                                 BM_faces_join(bm, faces, 2);
2240                 }
2241         }
2242 #endif
2243
2244         BMO_op_callf(bm, op->flag, "delete geom=%fv context=%i", BEVEL_DEL, DEL_VERTS);
2245
2246         /* clean up any edges that might not get properly delete */
2247         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
2248                 if (BMO_elem_flag_test(bm, e, EDGE_OLD) && !e->l)
2249                         BMO_elem_flag_enable(bm, e, BEVEL_DEL);
2250         }
2251
2252         BMO_op_callf(bm, op->flag, "delete geom=%fe context=%i", BEVEL_DEL, DEL_EDGES);
2253         BMO_op_callf(bm, op->flag, "delete geom=%ff context=%i", BEVEL_DEL, DEL_FACES);
2254         
2255         BLI_smallhash_release(&hash);
2256         BLI_array_free(tags);
2257         BLI_array_free(etags);
2258         BLI_array_free(verts);
2259         BLI_array_free(edges);
2260         BLI_array_free(faces);
2261         
2262         BMO_slot_buffer_from_enabled_flag(bm, op, "face_spans", BM_FACE, FACE_SPAN);
2263         BMO_slot_buffer_from_enabled_flag(bm, op, "face_holes", BM_FACE, FACE_HOLE);
2264 }
2265 #endif  /* NEW_BEVEL */