BMesh optimize face splitting by taking loops rather then verts
[blender.git] / source / blender / bmesh / tools / bmesh_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):
19  *         Joseph Eagar,
20  *         Aleksandr Mokhov,
21  *         Howard Trickey,
22  *         Campbell Barton
23  *
24  * ***** END GPL LICENSE BLOCK *****
25  */
26
27 /** \file blender/bmesh/tools/bmesh_bevel.c
28  *  \ingroup bmesh
29  */
30
31 #include "MEM_guardedalloc.h"
32
33 #include "DNA_object_types.h"
34 #include "DNA_meshdata_types.h"
35
36 #include "BLI_array.h"
37 #include "BLI_alloca.h"
38 #include "BLI_gsqueue.h"
39 #include "BLI_math.h"
40 #include "BLI_memarena.h"
41
42 #include "BKE_customdata.h"
43 #include "BKE_deform.h"
44
45 #include "bmesh.h"
46 #include "bmesh_bevel.h"  /* own include */
47
48 #include "./intern/bmesh_private.h"
49
50 #define BEVEL_EPSILON_D  1e-6
51 #define BEVEL_EPSILON    1e-6f
52
53 /* happens far too often, uncomment for development */
54 // #define BEVEL_ASSERT_PROJECT
55
56 /* for testing */
57 // #pragma GCC diagnostic error "-Wpadded"
58
59 /* Constructed vertex, sometimes later instantiated as BMVert */
60 typedef struct NewVert {
61         BMVert *v;
62         float co[3];
63 //      int _pad;
64 } NewVert;
65
66 struct BoundVert;
67
68 /* Data for one end of an edge involved in a bevel */
69 typedef struct EdgeHalf {
70         struct EdgeHalf *next, *prev;   /* in CCW order */
71         BMEdge *e;                  /* original mesh edge */
72         BMFace *fprev;              /* face between this edge and previous, if any */
73         BMFace *fnext;              /* face between this edge and next, if any */
74         struct BoundVert *leftv;    /* left boundary vert (looking along edge to end) */
75         struct BoundVert *rightv;   /* right boundary vert, if beveled */
76         int   seg;                  /* how many segments for the bevel */
77         float offset_l;             /* offset for this edge, on left side */
78         float offset_r;             /* offset for this edge, on right side */
79         float offset_l_spec;        /* user specification for offset_l */
80         float offset_r_spec;        /* user specification for offset_r */
81         bool is_bev;                /* is this edge beveled? */
82         bool is_rev;                /* is e->v2 the vertex at this end? */
83         bool is_seam;               /* is e a seam for custom loopdata (e.g., UVs)? */
84 //      int _pad;
85 } EdgeHalf;
86
87 /* An element in a cyclic boundary of a Vertex Mesh (VMesh) */
88 typedef struct BoundVert {
89         struct BoundVert *next, *prev;  /* in CCW order */
90         NewVert nv;
91         EdgeHalf *efirst;   /* first of edges attached here: in CCW order */
92         EdgeHalf *elast;
93         EdgeHalf *ebev;     /* beveled edge whose left side is attached here, if any */
94         int index;          /* used for vmesh indexing */
95         bool any_seam;      /* are any of the edges attached here seams? */
96 //      int _pad;
97 } BoundVert;
98
99 /* Mesh structure replacing a vertex */
100 typedef struct VMesh {
101         NewVert *mesh;           /* allocated array - size and structure depends on kind */
102         BoundVert *boundstart;   /* start of boundary double-linked list */
103         int count;               /* number of vertices in the boundary */
104         int seg;                 /* common # of segments for segmented edges */
105         enum {
106                 M_NONE,         /* no polygon mesh needed */
107                 M_POLY,         /* a simple polygon */
108                 M_ADJ,          /* "adjacent edges" mesh pattern */
109                 M_ADJ_SUBDIV,   /* like M_ADJ, but using subdivision */
110                 M_TRI_FAN,      /* a simple polygon - fan filled */
111                 M_QUAD_STRIP,   /* a simple polygon - cut into parallel strips */
112         } mesh_kind;
113 //      int _pad;
114 } VMesh;
115
116 /* Data for a vertex involved in a bevel */
117 typedef struct BevVert {
118         BMVert *v;          /* original mesh vertex */
119         int edgecount;          /* total number of edges around the vertex */
120         int selcount;           /* number of selected edges around the vertex */
121         float offset;           /* offset for this vertex, if vertex_only bevel */
122         bool any_seam;                  /* any seams on attached edges? */
123         bool visited;           /* used in graph traversal */
124         EdgeHalf *edges;        /* array of size edgecount; CCW order from vertex normal side */
125         VMesh *vmesh;           /* mesh structure for replacing vertex */
126 } BevVert;
127
128 /* Bevel parameters and state */
129 typedef struct BevelParams {
130         /* hash of BevVert for each vertex involved in bevel
131          * GHash: (key=(BMVert *), value=(BevVert *)) */
132         GHash    *vert_hash;
133         MemArena *mem_arena;    /* use for all allocs while bevel runs, if we need to free we can switch to mempool */
134
135         float offset;           /* blender units to offset each side of a beveled edge */
136         int offset_type;        /* how offset is measured; enum defined in bmesh_operators.h */
137         int seg;                /* number of segments in beveled edge profile */
138         bool vertex_only;       /* bevel vertices only */
139         bool use_weights;       /* bevel amount affected by weights on edges or verts */
140         bool preserve_widths;   /* should bevel prefer widths over angles, if forced to choose? */
141         bool limit_offset;      /* should offsets be limited by collisions? */
142         const struct MDeformVert *dvert; /* vertex group array, maybe set if vertex_only */
143         int vertex_group;       /* vertex group index, maybe set if vertex_only */
144 } BevelParams;
145
146 // #pragma GCC diagnostic ignored "-Wpadded"
147
148 // #include "bevdebug.c"
149
150 /* Make a new BoundVert of the given kind, insert it at the end of the circular linked
151  * list with entry point bv->boundstart, and return it. */
152 static BoundVert *add_new_bound_vert(MemArena *mem_arena, VMesh *vm, const float co[3])
153 {
154         BoundVert *ans = (BoundVert *)BLI_memarena_alloc(mem_arena, sizeof(BoundVert));
155
156         copy_v3_v3(ans->nv.co, co);
157         if (!vm->boundstart) {
158                 ans->index = 0;
159                 vm->boundstart = ans;
160                 ans->next = ans->prev = ans;
161         }
162         else {
163                 BoundVert *tail = vm->boundstart->prev;
164                 ans->index = tail->index + 1;
165                 ans->prev = tail;
166                 ans->next = vm->boundstart;
167                 tail->next = ans;
168                 vm->boundstart->prev = ans;
169         }
170         vm->count++;
171         return ans;
172 }
173
174 BLI_INLINE void adjust_bound_vert(BoundVert *bv, const float co[3])
175 {
176         copy_v3_v3(bv->nv.co, co);
177 }
178
179 /* Mesh verts are indexed (i, j, k) where
180  * i = boundvert index (0 <= i < nv)
181  * j = ring index (0 <= j <= ns2)
182  * k = segment index (0 <= k <= ns)
183  * Not all of these are used, and some will share BMVerts */
184 static NewVert *mesh_vert(VMesh *vm, int i, int j, int k)
185 {
186         int nj = (vm->seg / 2) + 1;
187         int nk = vm->seg + 1;
188
189         return &vm->mesh[i * nk * nj  + j * nk + k];
190 }
191
192 static void create_mesh_bmvert(BMesh *bm, VMesh *vm, int i, int j, int k, BMVert *eg)
193 {
194         NewVert *nv = mesh_vert(vm, i, j, k);
195         nv->v = BM_vert_create(bm, nv->co, eg, BM_CREATE_NOP);
196         BM_elem_flag_disable(nv->v, BM_ELEM_TAG);
197 }
198
199 static void copy_mesh_vert(VMesh *vm, int ito, int jto, int kto,
200                            int ifrom, int jfrom, int kfrom)
201 {
202         NewVert *nvto, *nvfrom;
203
204         nvto = mesh_vert(vm, ito, jto, kto);
205         nvfrom = mesh_vert(vm, ifrom, jfrom, kfrom);
206         nvto->v = nvfrom->v;
207         copy_v3_v3(nvto->co, nvfrom->co);
208 }
209
210 /* find the EdgeHalf in bv's array that has edge bme */
211 static EdgeHalf *find_edge_half(BevVert *bv, BMEdge *bme)
212 {
213         int i;
214
215         for (i = 0; i < bv->edgecount; i++) {
216                 if (bv->edges[i].e == bme)
217                         return &bv->edges[i];
218         }
219         return NULL;
220 }
221
222 /* find the BevVert corresponding to BMVert bmv */
223 static BevVert *find_bevvert(BevelParams *bp, BMVert *bmv)
224 {
225         return BLI_ghash_lookup(bp->vert_hash, bmv);
226 }
227
228 /* Find the EdgeHalf representing the other end of e->e.
229  * Return other end's BevVert in *bvother, if r_bvother is provided.
230  * That may not have been constructed yet, in which case return NULL. */
231 static EdgeHalf *find_other_end_edge_half(BevelParams *bp, EdgeHalf *e, BevVert **r_bvother)
232 {
233         BevVert *bvo;
234         EdgeHalf *eother;
235
236         bvo = find_bevvert(bp, e->is_rev ? e->e->v1 : e->e->v2);
237         if (bvo) {
238                 if (r_bvother)
239                         *r_bvother = bvo;
240                 eother = find_edge_half(bvo, e->e);
241                 BLI_assert(eother != NULL);
242                 return eother;
243         }
244         else if (r_bvother) {
245                 *r_bvother = NULL;
246         }
247         return NULL;
248 }
249
250 static bool other_edge_half_visited(BevelParams *bp, EdgeHalf *e)
251 {
252         BevVert *bvo;
253
254         bvo = find_bevvert(bp, e->is_rev ? e->e->v1 : e->e->v2);
255         if (bvo)
256                 return bvo->visited;
257         else
258                 return false;
259 }
260
261 static bool edge_half_offset_changed(EdgeHalf *e)
262 {
263         return e->offset_l != e->offset_l_spec ||
264                e->offset_r != e->offset_r_spec;
265 }
266
267 static bool any_edge_half_offset_changed(BevVert *bv)
268 {
269         int i;
270
271         for (i = 0; i < bv->edgecount; i++) {
272                 if (edge_half_offset_changed(&bv->edges[i]))
273                         return true;
274         }
275         return false;
276 }
277
278 /* Return the next EdgeHalf after from_e that is beveled.
279  * If from_e is NULL, find the first beveled edge. */
280 static EdgeHalf *next_bev(BevVert *bv, EdgeHalf *from_e)
281 {
282         EdgeHalf *e;
283
284         if (from_e == NULL)
285                 from_e = &bv->edges[bv->edgecount - 1];
286         e = from_e;
287         do {
288                 if (e->is_bev) {
289                         return e;
290                 }
291         } while ((e = e->next) != from_e);
292         return NULL;
293 }
294
295 /* Return a good representative face (for materials, etc.) for faces
296  * created around/near BoundVert v */
297 static BMFace *boundvert_rep_face(BoundVert *v)
298 {
299         BLI_assert(v->efirst != NULL && v->elast != NULL);
300         if (v->efirst->fnext == v->elast->fprev)
301                 return v->efirst->fnext;
302         else if (v->efirst->fnext)
303                 return v->efirst->fnext;
304         else
305                 return v->elast->fprev;
306 }
307
308 /**
309  * Make ngon from verts alone.
310  * Make sure to properly copy face attributes and do custom data interpolation from
311  * corresponding elements of face_arr, if that is non-NULL, else from facerep.
312  *
313  * \note ALL face creation goes through this function, this is important to keep!
314  */
315 static BMFace *bev_create_ngon(BMesh *bm, BMVert **vert_arr, const int totv,
316                                BMFace **face_arr, BMFace *facerep, bool do_interp)
317 {
318         BMIter iter;
319         BMLoop *l;
320         BMFace *f, *interp_f;
321         int i;
322
323         f = BM_face_create_verts(bm, vert_arr, totv, facerep, BM_CREATE_NOP, true);
324
325         if ((facerep || (face_arr && face_arr[0])) && f) {
326                 BM_elem_attrs_copy(bm, bm, facerep ? facerep : face_arr[0], f);
327                 if (do_interp) {
328                         i = 0;
329                         BM_ITER_ELEM (l, &iter, f, BM_LOOPS_OF_FACE) {
330                                 if (face_arr) {
331                                         /* assume loops of created face are in same order as verts */
332                                         BLI_assert(l->v == vert_arr[i]);
333                                         interp_f = face_arr[i];
334                                 }
335                                 else {
336                                         interp_f = facerep;
337                                 }
338                                 if (interp_f)
339                                         BM_loop_interp_from_face(bm, l, interp_f, TRUE, TRUE);
340                                 i++;
341                         }
342                 }
343         }
344
345         /* not essential for bevels own internal logic,
346          * this is done so the operator can select newly created faces */
347         if (f) {
348                 BM_elem_flag_enable(f, BM_ELEM_TAG);
349         }
350
351         return f;
352 }
353
354 static BMFace *bev_create_quad_tri(BMesh *bm, BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4,
355                                    BMFace *facerep, bool do_interp)
356 {
357         BMVert *varr[4] = {v1, v2, v3, v4};
358         return bev_create_ngon(bm, varr, v4 ? 4 : 3, NULL, facerep, do_interp);
359 }
360
361 static BMFace *bev_create_quad_tri_ex(BMesh *bm, BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4,
362                                       BMFace *f1, BMFace *f2, BMFace *f3, BMFace *f4)
363 {
364         BMVert *varr[4] = {v1, v2, v3, v4};
365         BMFace *farr[4] = {f1, f2, f3, f4};
366         return bev_create_ngon(bm, varr, v4 ? 4 : 3, farr, f1, true);
367 }
368
369
370 /* Is Loop layer layer_index contiguous across shared vertex of l1 and l2? */
371 static bool contig_ldata_across_loops(BMesh *bm, BMLoop *l1, BMLoop *l2,
372                                       int layer_index)
373 {
374         const int offset = bm->ldata.layers[layer_index].offset;
375         const int type = bm->ldata.layers[layer_index].type;
376
377         return CustomData_data_equals(type,
378                                       (char *)l1->head.data + offset,
379                                       (char *)l2->head.data + offset);
380 }
381
382 /* Are all loop layers with have math (e.g., UVs) contiguous from face f1 to face f2 across edge e? */
383 static bool contig_ldata_across_edge(BMesh *bm, BMEdge *e, BMFace *f1, BMFace *f2)
384 {
385         BMLoop *lef1, *lef2;
386         BMLoop *lv1f1, *lv1f2, *lv2f1, *lv2f2;
387         BMVert *v1, *v2;
388         int i;
389
390         if (bm->ldata.totlayer == 0)
391                 return true;
392
393         v1 = e->v1;
394         v2 = e->v2;
395         if (!BM_edge_loop_pair(e, &lef1, &lef2))
396                 return false;
397         if (lef1->f == f2) {
398                 SWAP(BMLoop *, lef1, lef2);
399         }
400
401         if (lef1->v == v1) {
402                 lv1f1 = lef1;
403                 lv2f1 = BM_face_other_edge_loop(f1, e, v2);
404         }
405         else {
406                 lv2f1 = lef1;
407                 lv1f1 = BM_face_other_edge_loop(f1, e, v1);
408         }
409
410         if (lef2->v == v1) {
411                 lv1f2 = lef2;
412                 lv2f2 = BM_face_other_edge_loop(f2, e, v2);
413         }
414         else {
415                 lv2f2 = lef2;
416                 lv1f2 = BM_face_other_edge_loop(f2, e, v1);
417         }
418
419         for (i = 0; i < bm->ldata.totlayer; i++) {
420                 if (CustomData_layer_has_math(&bm->ldata, i) &&
421                     (!contig_ldata_across_loops(bm, lv1f1, lv1f2, i) ||
422                      !contig_ldata_across_loops(bm, lv2f1, lv2f2, i)))
423                 {
424                         return false;
425                 }
426         }
427         return true;
428 }
429
430 /* Like bev_create_quad_tri, but when verts straddle an old edge.
431  *        e
432  *        |
433  *  v1+---|---+v4
434  *    |   |   |
435  *    |   |   |
436  *  v2+---|---+v3
437  *        |
438  *    f1  |  f2
439  *
440  * Most CustomData for loops can be interpolated in their respective
441  * faces' loops, but for UVs and other 'has_math_cd' layers, only
442  * do this if the UVs are continuous across the edge e, otherwise pick
443  * one side (f1, arbitrarily), and interpolate them all on that side.
444  * For face data, use f1 (arbitrarily) as face representative. */
445 static BMFace *bev_create_quad_straddle(BMesh *bm, BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4,
446         BMFace *f1, BMFace *f2, bool is_seam)
447 {
448         BMFace *f, *facerep;
449         BMLoop *l;
450         BMIter iter;
451
452         f = bev_create_quad_tri(bm, v1, v2, v3, v4, f1, false);
453
454         if (!f)
455                 return NULL;
456
457         BM_ITER_ELEM (l, &iter, f, BM_LOOPS_OF_FACE) {
458                 if (is_seam || l->v == v1 || l->v == v2)
459                         facerep = f1;
460                 else
461                         facerep = f2;
462                 if (facerep)
463                         BM_loop_interp_from_face(bm, l, facerep, TRUE, TRUE);
464         }
465         return f;
466 }
467
468 /* Merge (using average) all the UV values for loops of v's faces.
469  * Caller should ensure that no seams are violated by doing this. */
470 static void bev_merge_uvs(BMesh *bm, BMVert *v)
471 {
472         BMIter iter;
473         MLoopUV *luv;
474         BMLoop *l;
475         float uv[2];
476         int n;
477         int cd_loop_uv_offset = CustomData_get_offset(&bm->ldata, CD_MLOOPUV);
478
479         if (cd_loop_uv_offset == -1)
480                 return;
481
482         n = 0;
483         zero_v2(uv);
484         BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
485                 luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
486                 add_v2_v2(uv, luv->uv);
487                 n++;
488         }
489         if (n > 1) {
490                 mul_v2_fl(uv, 1.0f / (float)n);
491                 BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
492                         luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
493                         copy_v2_v2(luv->uv, uv);
494                 }
495         }
496 }
497
498 /* Calculate coordinates of a point a distance d from v on e->e and return it in slideco */
499 static void slide_dist(EdgeHalf *e, BMVert *v, float d, float slideco[3])
500 {
501         float dir[3], len;
502
503         sub_v3_v3v3(dir, v->co, BM_edge_other_vert(e->e, v)->co);
504         len = normalize_v3(dir);
505         if (d > len)
506                 d = len - (float)(50.0 * BEVEL_EPSILON_D);
507         copy_v3_v3(slideco, v->co);
508         madd_v3_v3fl(slideco, dir, -d);
509 }
510
511 /*
512  * Calculate the meeting point between the offset edges for e1 and e2, putting answer in meetco.
513  * e1 and e2 share vertex v and face f (may be NULL) and viewed from the normal side of
514  * the bevel vertex,  e1 precedes e2 in CCW order.
515  * Offset edge is on right of both edges, where e1 enters v and e2 leave it.
516  * When offsets are equal, the new point is on the edge bisector, with length offset/sin(angle/2),
517  * but if the offsets are not equal (allowing for this, as bevel modifier has edge weights that may
518  * lead to different offsets) then meeting point can be found be intersecting offset lines.
519  * If making the meeting point significantly changes the left or right offset from the user spec,
520  * record the change in offset_l (or offset_r); later we can tell that a change has happened because
521  * the offset will differ from its original value in offset_l_spec (or offset_r_spec).
522  */
523 static void offset_meet(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, BMFace *f, float meetco[3])
524 {
525         float dir1[3], dir2[3], norm_v[3], norm_perp1[3], norm_perp2[3],
526               off1a[3], off1b[3], off2a[3], off2b[3], isect2[3], ang, d;
527
528         /* get direction vectors for two offset lines */
529         sub_v3_v3v3(dir1, v->co, BM_edge_other_vert(e1->e, v)->co);
530         sub_v3_v3v3(dir2, BM_edge_other_vert(e2->e, v)->co, v->co);
531
532         ang = angle_v3v3(dir1, dir2);
533         if (ang < 100.0f * BEVEL_EPSILON) {
534                 /* special case: e1 and e2 are parallel; put offset point perp to both, from v.
535                  * need to find a suitable plane.
536                  * if offsets are different, we're out of luck: just use e1->offset_r */
537                 if (f)
538                         copy_v3_v3(norm_v, f->no);
539                 else
540                         copy_v3_v3(norm_v, v->no);
541                 cross_v3_v3v3(norm_perp1, dir1, norm_v);
542                 normalize_v3(norm_perp1);
543                 copy_v3_v3(off1a, v->co);
544                 madd_v3_v3fl(off1a, norm_perp1, e1->offset_r);
545                 if (e2->offset_l != e1->offset_r)
546                         e2->offset_l = e1->offset_r;
547                 copy_v3_v3(meetco, off1a);
548         }
549         else if (fabsf(ang - (float)M_PI) < 100.0f * BEVEL_EPSILON) {
550                 /* special case e1 and e2 are antiparallel, so bevel is into
551                  * a zero-area face.  Just make the offset point on the
552                  * common line, at offset distance from v. */
553                 slide_dist(e2, v, e1->offset_r, meetco);
554                 if (e2->offset_l != e1->offset_r)
555                         e2->offset_l = e1->offset_r;
556         }
557         else {
558                 /* Get normal to plane where meet point should be,
559                  * using cross product instead of f->no in case f is non-planar.
560                  * If e1-v-e2 is a reflex angle (viewed from vertex normal side), need to flip*/
561                 cross_v3_v3v3(norm_v, dir2, dir1);
562                 normalize_v3(norm_v);
563                 if (dot_v3v3(norm_v, v->no) < 0.0f)
564                         negate_v3(norm_v);
565
566                 /* get vectors perp to each edge, perp to norm_v, and pointing into face */
567                 cross_v3_v3v3(norm_perp1, dir1, norm_v);
568                 cross_v3_v3v3(norm_perp2, dir2, norm_v);
569                 normalize_v3(norm_perp1);
570                 normalize_v3(norm_perp2);
571
572                 /* get points that are offset distances from each line, then another point on each line */
573                 copy_v3_v3(off1a, v->co);
574                 madd_v3_v3fl(off1a, norm_perp1, e1->offset_r);
575                 add_v3_v3v3(off1b, off1a, dir1);
576                 copy_v3_v3(off2a, v->co);
577                 madd_v3_v3fl(off2a, norm_perp2, e2->offset_l);
578                 add_v3_v3v3(off2b, off2a, dir2);
579
580                 /* intersect the lines; by construction they should be on the same plane and not parallel */
581                 if (!isect_line_line_v3(off1a, off1b, off2a, off2b, meetco, isect2)) {
582 #ifdef BEVEL_ASSERT_PROJECT
583                         BLI_assert(!"offset_meet failure");
584 #endif
585                         copy_v3_v3(meetco, off1a);  /* just to do something */
586                         d = dist_to_line_v3(meetco, v->co, BM_edge_other_vert(e2->e, v)->co);
587                         if (fabsf(d - e2->offset_l) > BEVEL_EPSILON)
588                                 e2->offset_l = d;
589                 }
590         }
591 }
592
593 /* Calculate the meeting point between e1 and e2 (one of which should have zero offsets),
594  * where e1 precedes e2 in CCW order around their common vertex v (viewed from normal side).
595  * If r_angle is provided, return the angle between e and emeet in *r_angle.
596  * If the angle is 0, or it is 180 degrees or larger, there will be no meeting point;
597  * return false in that case, else true */
598 static bool offset_meet_edge(EdgeHalf *e1, EdgeHalf *e2, BMVert *v,  float meetco[3], float *r_angle)
599 {
600         float dir1[3], dir2[3], fno[3], ang, sinang;
601
602         sub_v3_v3v3(dir1, BM_edge_other_vert(e1->e, v)->co, v->co);
603         sub_v3_v3v3(dir2, BM_edge_other_vert(e2->e, v)->co, v->co);
604         normalize_v3(dir1);
605         normalize_v3(dir2);
606
607         /* find angle from dir1 to dir2 as viewed from vertex normal side */
608         ang = angle_normalized_v3v3(dir1, dir2);
609         if (ang < BEVEL_EPSILON) {
610                 if (r_angle)
611                         *r_angle = 0.0f;
612                 return false;
613         }
614         cross_v3_v3v3(fno, dir1, dir2);
615         if (dot_v3v3(fno, v->no) < 0.0f)
616                 ang = 2.0f * (float)M_PI - ang;  /* angle is reflex */
617         if (r_angle)
618                 *r_angle = ang;
619
620         if (ang - (float)M_PI > BEVEL_EPSILON)
621                 return false;
622
623         sinang = sinf(ang);
624         copy_v3_v3(meetco, v->co);
625         if (e1->offset_r == 0.0f)
626                 madd_v3_v3fl(meetco, dir1, e2->offset_l / sinang);
627         else
628                 madd_v3_v3fl(meetco, dir2, e1->offset_r / sinang);
629         return true;
630 }
631
632 /* Calculate the best place for a meeting point for the offsets from edges e1 and e2
633  * on the in-between edge emid.  Viewed from the vertex normal side, the CCW
634  * order of these edges is e1, emid, e2.
635  * The offsets probably do not meet at a common point on emid, so need to pick
636  * one that causes the least problems. If the other end of one of e1 or e2 has been visited
637  * already, prefer to keep the offset the same on this end.
638  * Otherwise, pick a point between the two intersection points on emid that minimizes
639  * the sum of squares of errors from desired offset. */
640 static void offset_on_edge_between(BevelParams *bp, EdgeHalf *e1, EdgeHalf *e2, EdgeHalf *emid,
641                                    BMVert *v, float meetco[3])
642 {
643         float d, ang1, ang2, sina1, sina2, lambda;
644         float meet1[3], meet2[3];
645         bool visited1, visited2, ok1, ok2;
646
647         BLI_assert(e1->is_bev && e2->is_bev && !emid->is_bev);
648
649         visited1 = other_edge_half_visited(bp, e1);
650         visited2 = other_edge_half_visited(bp, e2);
651
652         ok1 = offset_meet_edge(e1, emid, v, meet1, &ang1);
653         ok2 = offset_meet_edge(emid, e2, v, meet2, &ang2);
654         if (ok1 && ok2) {
655                 if (visited1 && !visited2) {
656                         copy_v3_v3(meetco, meet1);
657                 }
658                 else if (!visited1 && visited2) {
659                         copy_v3_v3(meetco, meet2);
660                 }
661                 else {
662                         /* find best compromise meet point */
663                         sina1 = sinf(ang1);
664                         sina2 = sinf(ang2);
665                         lambda = sina2 * sina2 / (sina1 * sina1 + sina2 * sina2);
666                         interp_v3_v3v3(meetco, meet1, meet2, lambda);
667                 }
668         }
669         else if (ok1 && !ok2) {
670                 copy_v3_v3(meetco, meet1);
671         }
672         else if (!ok1 && ok2) {
673                 copy_v3_v3(meetco, meet2);
674         }
675         else {
676                 /* Neither offset line met emid.
677                  * This should only happen if all three lines are on top of each other */
678                 slide_dist(emid, v, e1->offset_r, meetco);
679         }
680
681         /* offsets may have changed now */
682         d = dist_to_line_v3(meetco, v->co, BM_edge_other_vert(e1->e, v)->co);
683         if (fabsf(d - e1->offset_r) > BEVEL_EPSILON)
684                 e1->offset_r = d;
685         d = dist_to_line_v3(meetco, v->co, BM_edge_other_vert(e2->e, v)->co);
686         if (fabsf(d - e2->offset_l) > BEVEL_EPSILON)
687                 e2->offset_l = d;
688 }
689
690 /* Calculate the best place for a meeting point for the offsets from edges e1 and e2
691  * when there is an in-between edge emid, and we prefer to have a point that may not
692  * be on emid if that does a better job of keeping offsets at the user spec.
693  * Viewed from the vertex normal side, the CCW order of the edges is e1, emid, e2.
694  * The offset lines may not meet exactly: the lines may be angled so that they can't meet.
695  * In that case, pick  the the offset_on_edge_between. */
696 static void offset_in_two_planes(BevelParams *bp, EdgeHalf *e1, EdgeHalf *e2, EdgeHalf *emid,
697                                  BMVert *v,  float meetco[3])
698 {
699         float dir1[3], dir2[3], dirmid[3], norm_perp1[3], norm_perp2[3],
700               off1a[3], off1b[3], off2a[3], off2b[3], isect2[3],
701               f1no[3], f2no[3], ang, d;
702         int iret;
703
704         /* get direction vectors for two offset lines */
705         sub_v3_v3v3(dir1, v->co, BM_edge_other_vert(e1->e, v)->co);
706         sub_v3_v3v3(dir2, BM_edge_other_vert(e2->e, v)->co, v->co);
707         sub_v3_v3v3(dirmid, BM_edge_other_vert(emid->e, v)->co, v->co);
708
709         /* get directions into offset planes */
710         /* calculate face normals at corner in case faces are nonplanar */
711         cross_v3_v3v3(f1no, dirmid, dir1);
712         cross_v3_v3v3(f2no, dirmid, dir2);
713
714         /* if e1-v-emid or emid-v-e2 are reflex angles, need to flip corner normals */
715         if (dot_v3v3(f1no, v->no) < 0.0f)
716                 negate_v3(f1no);
717         if (dot_v3v3(f2no, v->no) < 0.0f)
718                 negate_v3(f2no);
719
720         /* get vectors perpendicular to e1 and e2, pointing into the proper faces */
721         cross_v3_v3v3(norm_perp1, dir1, f1no);
722         normalize_v3(norm_perp1);
723         cross_v3_v3v3(norm_perp2, dir2, f2no);
724         normalize_v3(norm_perp2);
725
726         /* get points that are offset distances from each line, then another point on each line */
727         copy_v3_v3(off1a, v->co);
728         madd_v3_v3fl(off1a, norm_perp1, e1->offset_r);
729         sub_v3_v3v3(off1b, off1a, dir1);
730         copy_v3_v3(off2a, v->co);
731         madd_v3_v3fl(off2a, norm_perp2, e2->offset_l);
732         add_v3_v3v3(off2b, off2a, dir2);
733
734         ang = angle_v3v3(dir1, dir2);
735         if (ang < 100.0f * BEVEL_EPSILON) {
736                 /* lines are parallel; put intersection on emid */
737                 offset_on_edge_between(bp, e1, e2, emid, v, meetco);
738         }
739         else if (fabsf(ang - (float)M_PI) < 100.0f * BEVEL_EPSILON) {
740                 slide_dist(e2, v, e2->offset_l, meetco);
741                 d = dist_to_line_v3(meetco, v->co, BM_edge_other_vert(e1->e, v)->co);
742                 if (fabsf(d - e1->offset_r) > BEVEL_EPSILON)
743                         e1->offset_r = d;
744         }
745         else {
746                 iret = isect_line_line_v3(off1a, off1b, off2a, off2b, meetco, isect2);
747                 if (iret == 0) {
748                         /* lines colinear: another test says they are parallel. so shouldn't happen */
749                         copy_v3_v3(meetco, off1a);
750                         d = dist_to_line_v3(meetco, v->co, BM_edge_other_vert(e2->e, v)->co);
751                         if (fabsf(d - e2->offset_l) > BEVEL_EPSILON)
752                                 e2->offset_l = d;
753                 }
754                 else if (iret == 2) {
755                         /* lines are not coplanar and don't meet; meetco and isect2 are nearest to first and second lines */
756                         if (len_v3v3(meetco, isect2) > 100.0f * BEVEL_EPSILON) {
757                                 /* offset lines don't meet so can't preserve widths */
758                                 offset_on_edge_between(bp, e1, e2, emid, v, meetco);
759                         }
760                 }
761                 /* else iret == 1 and the lines are coplanar so meetco has the intersection */
762         }
763 }
764
765 /* Offset by e->offset in plane with normal plane_no, on left if left==TRUE,
766  * else on right.  If no is NULL, choose an arbitrary plane different
767  * from eh's direction. */
768 static void offset_in_plane(EdgeHalf *e, const float plane_no[3], int left, float r[3])
769 {
770         float dir[3], no[3], fdir[3];
771         BMVert *v;
772
773         v = e->is_rev ? e->e->v2 : e->e->v1;
774
775         sub_v3_v3v3(dir, BM_edge_other_vert(e->e, v)->co, v->co);
776         normalize_v3(dir);
777         if (plane_no) {
778                 copy_v3_v3(no, plane_no);
779         }
780         else {
781                 zero_v3(no);
782                 if (fabsf(dir[0]) < fabsf(dir[1]))
783                         no[0] = 1.0f;
784                 else
785                         no[1] = 1.0f;
786         }
787         if (left)
788                 cross_v3_v3v3(fdir, dir, no);
789         else
790                 cross_v3_v3v3(fdir, no, dir);
791         normalize_v3(fdir);
792         copy_v3_v3(r, v->co);
793         madd_v3_v3fl(r, fdir, left? e->offset_l : e->offset_r);
794 }
795
796 /* Calculate the point on e where line (co_a, co_b) comes closest to and return it in projco */
797 static void project_to_edge(BMEdge *e, const float co_a[3], const float co_b[3], float projco[3])
798 {
799         float otherco[3];
800
801         if (!isect_line_line_v3(e->v1->co, e->v2->co, co_a, co_b, projco, otherco)) {
802 #ifdef BEVEL_ASSERT_PROJECT
803                 BLI_assert(!"project meet failure");
804 #endif
805                 copy_v3_v3(projco, e->v1->co);
806         }
807 }
808
809 /* return 1 if a and b are in CCW order on the normal side of f,
810  * and -1 if they are reversed, and 0 if there is no shared face f */
811 static int bev_ccw_test(BMEdge *a, BMEdge *b, BMFace *f)
812 {
813         BMLoop *la, *lb;
814
815         if (!f)
816                 return 0;
817         la = BM_face_edge_share_loop(f, a);
818         lb = BM_face_edge_share_loop(f, b);
819         if (!la || !lb)
820                 return 0;
821         return lb->next == la ? 1 : -1;
822 }
823
824 /* Fill matrix r_mat so that a point in the sheared parallelogram with corners
825  * va, vmid, vb (and the 4th that is implied by it being a parallelogram)
826  * is transformed to the unit square by multiplication with r_mat.
827  * If it can't be done because the parallelogram is degenerate, return FALSE
828  * else return TRUE.
829  * Method:
830  * Find vo, the origin of the parallelogram with other three points va, vmid, vb.
831  * Also find vd, which is in direction normal to parallelogram and 1 unit away
832  * from the origin.
833  * The quarter circle in first quadrant of unit square will be mapped to the
834  * quadrant of a sheared ellipse in the parallelogram, using a matrix.
835  * The matrix mat is calculated to map:
836  *    (0,1,0) -> va
837  *    (1,1,0) -> vmid
838  *    (1,0,0) -> vb
839  *    (0,1,1) -> vd
840  * We want M to make M*A=B where A has the left side above, as columns
841  * and B has the right side as columns - both extended into homogeneous coords.
842  * So M = B*(Ainverse).  Doing Ainverse by hand gives the code below.
843  */
844 static int make_unit_square_map(const float va[3], const float vmid[3], const float vb[3],
845                                 float r_mat[4][4])
846 {
847         float vo[3], vd[3], vb_vmid[3], va_vmid[3], vddir[3];
848
849         sub_v3_v3v3(va_vmid, vmid, va);
850         sub_v3_v3v3(vb_vmid, vmid, vb);
851         if (fabsf(angle_v3v3(va_vmid, vb_vmid) - (float)M_PI) > 100.0f * BEVEL_EPSILON) {
852                 sub_v3_v3v3(vo, va, vb_vmid);
853                 cross_v3_v3v3(vddir, vb_vmid, va_vmid);
854                 normalize_v3(vddir);
855                 add_v3_v3v3(vd, vo, vddir);
856
857                 /* The cols of m are: {vmid - va, vmid - vb, vmid + vd - va -vb, va + vb - vmid;
858                  * blender transform matrices are stored such that m[i][*] is ith column;
859                  * the last elements of each col remain as they are in unity matrix */
860                 sub_v3_v3v3(&r_mat[0][0], vmid, va);
861                 r_mat[0][3] = 0.0f;
862                 sub_v3_v3v3(&r_mat[1][0], vmid, vb);
863                 r_mat[1][3] = 0.0f;
864                 add_v3_v3v3(&r_mat[2][0], vmid, vd);
865                 sub_v3_v3(&r_mat[2][0], va);
866                 sub_v3_v3(&r_mat[2][0], vb);
867                 r_mat[2][3] = 0.0f;
868                 add_v3_v3v3(&r_mat[3][0], va, vb);
869                 sub_v3_v3(&r_mat[3][0], vmid);
870                 r_mat[3][3] = 1.0f;
871
872                 return TRUE;
873         }
874         else
875                 return FALSE;
876 }
877
878 /*
879  * Find the point (/n) of the way around the round profile for e,
880  * where start point is va, midarc point is vmid, and end point is vb.
881  * Return the answer in profileco.
882  * If va -- vmid -- vb is approximately a straight line, just
883  * interpolate along the line.
884  */
885 static void get_point_on_round_edge(EdgeHalf *e, int k,
886                                     const float va[3], const float vmid[3], const float vb[3],
887                                     float r_co[3])
888 {
889         float p[3], angle;
890         float m[4][4];
891         int n = e->seg;
892
893         if (make_unit_square_map(va, vmid, vb, m)) {
894                 /* Find point k/(e->seg) along quarter circle from (0,1,0) to (1,0,0) */
895                 angle = (float)M_PI * (float)k / (2.0f * (float)n);  /* angle from y axis */
896                 p[0] = sinf(angle);
897                 p[1] = cosf(angle);
898                 p[2] = 0.0f;
899                 mul_v3_m4v3(r_co, m, p);
900         }
901         else {
902                 /* degenerate case: profile is a line */
903                 interp_v3_v3v3(r_co, va, vb, (float)k / (float)n);
904         }
905 }
906
907 /* Calculate a snapped point to the transformed profile of edge e, extended as
908  * in a cylinder-like surface in the direction of e.
909  * co is the point to snap and is modified in place.
910  * va and vb are the limits of the profile (with peak on e). */
911 static void snap_to_edge_profile(EdgeHalf *e, const float va[3], const float vb[3],
912                                  float co[3])
913 {
914         float m[4][4], minv[4][4];
915         float edir[3], va0[3], vb0[3], vmid0[3], p[3], snap[3], plane[4];
916
917         sub_v3_v3v3(edir, e->e->v1->co, e->e->v2->co);
918
919         /* project va and vb onto plane P, with normal edir and containing co */
920         plane_from_point_normal_v3(plane, co, edir);
921         closest_to_plane_v3(va0, plane, va);
922         closest_to_plane_v3(vb0, plane, vb);
923         project_to_edge(e->e, va0, vb0, vmid0);
924         if (make_unit_square_map(va0, vmid0, vb0, m)) {
925                 /* Transform co and project it onto the unit circle.
926                  * Projecting is in fact just normalizing the transformed co */
927                 if (!invert_m4_m4(minv, m)) {
928                         /* shouldn't happen, by angle test and construction of vd */
929                         BLI_assert(!"failed inverse during profile snap");
930                         return;
931                 }
932                 mul_v3_m4v3(p, minv, co);
933                 normalize_v3(p);
934                 mul_v3_m4v3(snap, m, p);
935                 copy_v3_v3(co, snap);
936         }
937         else {
938                 /* planar case: just snap to line va--vb */
939                 closest_to_line_segment_v3(p, co, va, vb);
940                 copy_v3_v3(co, p);
941         }
942 }
943
944 /* Set the any_seam property for a BevVert and all its BoundVerts */
945 static void set_bound_vert_seams(BevVert *bv)
946 {
947         BoundVert *v;
948         EdgeHalf *e;
949
950         bv->any_seam = false;
951         v = bv->vmesh->boundstart;
952         do {
953                 v->any_seam = false;
954                 for (e = v->efirst; e; e = e->next) {
955                         v->any_seam |= e->is_seam;
956                         if (e == v->elast)
957                                 break;
958                 }
959                 bv->any_seam |= v->any_seam;
960         } while ((v = v->next) != bv->vmesh->boundstart);
961 }
962
963 /* Make a circular list of BoundVerts for bv, each of which has the coordinates
964  * of a vertex on the the boundary of the beveled vertex bv->v.
965  * This may adjust some EdgeHalf widths, and there might have to be
966  * a subsequent pass to make the widths as consistent as possible.
967  * The first time through, construct will be true and we are making the BoundVerts
968  * and setting up the BoundVert and EdgeHalf pointers appropriately.
969  * For a width consistency path, we just recalculate the coordinates of the
970  * BoundVerts. If the other ends have been (re)built already, then we
971  * copy the offsets from there to match, else we use the ideal (user-specified)
972  * widths.
973  * Also, if construct, decide on the mesh pattern that will be used inside the boundary.
974  * Doesn't make the actual BMVerts */
975 static void build_boundary(BevelParams *bp, BevVert *bv, bool construct)
976 {
977         MemArena *mem_arena = bp->mem_arena;
978         EdgeHalf *efirst, *e, *eother;
979         BoundVert *v;
980         BevVert *bvother;
981         VMesh *vm;
982         float co[3];
983         const float  *no;
984         float lastd;
985
986         vm = bv->vmesh;
987
988         if (bp->vertex_only) {
989                 e = efirst = &bv->edges[0];
990         }
991         else {
992                 e = efirst = next_bev(bv, NULL);
993                 do {
994                         eother = find_other_end_edge_half(bp, e, &bvother);
995                         if (eother && bvother->visited && bp->offset_type != BEVEL_AMT_PERCENT) {
996                                 /* try to keep bevel even by matching other end offsets */
997                                 e->offset_l = eother->offset_r;
998                                 e->offset_r = eother->offset_l;
999                         }
1000                         else {
1001                                 /* reset to user spec */
1002                                 e->offset_l = e->offset_l_spec;
1003                                 e->offset_r = e->offset_r_spec;
1004                         }
1005                 } while ((e = e->next) != efirst);
1006                 e = efirst;
1007         }
1008
1009         BLI_assert(bv->edgecount >= 2);  /* since bevel edges incident to 2 faces */
1010
1011         if (bv->edgecount == 2 && bv->selcount == 1) {
1012                 /* special case: beveled edge meets non-beveled one at valence 2 vert */
1013                 no = e->fprev ? e->fprev->no : (e->fnext ? e->fnext->no : NULL);
1014                 offset_in_plane(e, no, TRUE, co);
1015                 if (construct) {
1016                         v = add_new_bound_vert(mem_arena, vm, co);
1017                         v->efirst = v->elast = v->ebev = e;
1018                         e->leftv = v;
1019                 }
1020                 else {
1021                         adjust_bound_vert(e->leftv, co);
1022                 }
1023                 no = e->fnext ? e->fnext->no : (e->fprev ? e->fprev->no : NULL);
1024                 offset_in_plane(e, no, FALSE, co);
1025                 if (construct) {
1026                         v = add_new_bound_vert(mem_arena, vm, co);
1027                         v->efirst = v->elast = e;
1028                         e->rightv = v;
1029                 }
1030                 else {
1031                         adjust_bound_vert(e->rightv, co);
1032                 }
1033                 /* make artifical extra point along unbeveled edge, and form triangle */
1034                 slide_dist(e->next, bv->v, e->offset_l, co);
1035                 if (construct) {
1036                         v = add_new_bound_vert(mem_arena, vm, co);
1037                         v->efirst = v->elast = e->next;
1038                         e->next->leftv = e->next->rightv = v;
1039                         /* could use M_POLY too, but tri-fan looks nicer)*/
1040                         vm->mesh_kind = M_TRI_FAN;
1041                         set_bound_vert_seams(bv);
1042                 }
1043                 else {
1044                         adjust_bound_vert(e->next->leftv, co);
1045                 }
1046                 return;
1047         }
1048
1049         lastd = bp->vertex_only ? bv->offset : e->offset_l;
1050         do {
1051                 if (e->is_bev) {
1052                         /* handle only left side of beveled edge e here: next iteration should do right side */
1053                         if (e->prev->is_bev) {
1054                                 BLI_assert(e->prev != e);  /* see: wire edge special case */
1055                                 offset_meet(e->prev, e, bv->v, e->fprev, co);
1056                                 if (construct) {
1057                                         v = add_new_bound_vert(mem_arena, vm, co);
1058                                         v->efirst = e->prev;
1059                                         v->elast = v->ebev = e;
1060                                         e->leftv = v;
1061                                         e->prev->rightv = v;
1062                                 }
1063                                 else {
1064                                         v = e->leftv;
1065                                         adjust_bound_vert(v, co);
1066                                 }
1067                         }
1068                         else {
1069                                 /* e->prev is not beveled */
1070                                 if (e->prev->prev->is_bev) {
1071                                         BLI_assert(e->prev->prev != e); /* see: edgecount 2, selcount 1 case */
1072                                         /* find meet point between e->prev->prev and e and attach e->prev there */
1073                                         if (bp->preserve_widths)
1074                                                 offset_in_two_planes(bp, e->prev->prev, e, e->prev, bv->v, co);
1075                                         else
1076                                                 offset_on_edge_between(bp, e->prev->prev, e, e->prev, bv->v, co);
1077                                         if (construct) {
1078                                                 v = add_new_bound_vert(mem_arena, vm, co);
1079                                                 v->efirst = e->prev->prev;
1080                                                 v->elast = v->ebev = e;
1081                                                 e->leftv = v;
1082                                                 e->prev->leftv = v;
1083                                                 e->prev->prev->rightv = v;
1084                                         }
1085                                         else {
1086                                                 v = e->leftv;
1087                                                 adjust_bound_vert(v, co);
1088                                         }
1089                                 }
1090                                 else {
1091                                         /* neither e->prev nor e->prev->prev are beveled: make on-edge on e->prev */
1092                                         offset_meet(e->prev, e, bv->v, e->fprev, co);
1093                                         if (construct) {
1094                                                 v = add_new_bound_vert(mem_arena, vm, co);
1095                                                 v->efirst = e->prev;
1096                                                 v->elast = v->ebev = e;
1097                                                 e->leftv = v;
1098                                                 e->prev->leftv = v;
1099                                         }
1100                                         else {
1101                                                 v = e->leftv;
1102                                                 adjust_bound_vert(v, co);
1103                                         }
1104                                 }
1105                         }
1106                         lastd = len_v3v3(bv->v->co, v->nv.co);
1107                 }
1108                 else {
1109                         /* e is not beveled */
1110                         if (e->next->is_bev) {
1111                                 /* next iteration will place e between beveled previous and next edges */
1112                                 /* do nothing... */
1113                         }
1114                         else if (e->prev->is_bev) {
1115                                 /* on-edge meet between e->prev and e */
1116                                 offset_meet(e->prev, e, bv->v, e->fprev, co);
1117                                 if (construct) {
1118                                         v = add_new_bound_vert(mem_arena, vm, co);
1119                                         v->efirst = e->prev;
1120                                         v->elast = e;
1121                                         e->leftv = v;
1122                                         e->prev->rightv = v;
1123                                 }
1124                                 else {
1125                                         adjust_bound_vert(e->leftv, co);
1126                                 }
1127                         }
1128                         else {
1129                                 /* None of e->prev, e, e->next are beveled.
1130                                  * could either leave alone or add slide points to make
1131                                  * one polygon around bv->v.  For now, we choose latter.
1132                                  * Could slide to make an even bevel plane but for now will
1133                                  * just use last distance a meet point moved from bv->v. */
1134                                 slide_dist(e, bv->v, lastd, co);
1135                                 if (construct) {
1136                                         v = add_new_bound_vert(mem_arena, vm, co);
1137                                         v->efirst = v->elast = e;
1138                                         e->leftv = v;
1139                                 }
1140                                 else {
1141                                         adjust_bound_vert(e->leftv, co);
1142                                 }
1143                         }
1144                 }
1145         } while ((e = e->next) != efirst);
1146
1147         if (construct) {
1148                 set_bound_vert_seams(bv);
1149
1150                 BLI_assert(vm->count >= 2);
1151                 if (bp->vertex_only) {
1152                         if (vm->count == 2)
1153                                 vm->mesh_kind = M_NONE;
1154                         else if (bp->seg > 1)
1155                                 vm->mesh_kind = M_ADJ_SUBDIV;
1156                         else
1157                                 vm->mesh_kind = M_POLY;
1158                 }
1159                 else if (vm->count == 2 && bv->edgecount == 3) {
1160                         vm->mesh_kind = M_NONE;
1161                 }
1162                 else if (bv->selcount == 2) {
1163                         vm->mesh_kind = M_QUAD_STRIP;
1164                 }
1165                 else if (efirst->seg == 1 || bv->selcount == 1) {
1166                         if (vm->count == 3 && bv->selcount == 1) {
1167                                 vm->mesh_kind = M_TRI_FAN;
1168                         }
1169                         else {
1170                                 vm->mesh_kind = M_POLY;
1171                         }
1172                 }
1173                 else {
1174                         vm->mesh_kind = M_ADJ;
1175                 }
1176         }
1177 }
1178
1179 /* Do a global pass to try to make offsets as even as possible.
1180  * Consider this graph:
1181  *   nodes = BevVerts
1182  *   edges = { (u,v) } where u and v are nodes such that u and v
1183  *        are connected by a mesh edge that has at least one end
1184  *        whose offset does not match the user spec.
1185  *
1186  * Do a breadth-first search on this graph, starting from nodes
1187  * that have any_adjust=true, and changing all
1188  * not-already-changed offsets on EdgeHalfs to match the
1189  * corresponding ones that changed on the other end.
1190  * The graph is dynamic in the sense that having an offset that
1191  * doesn't meet the user spec can be added as the search proceeds.
1192  * We want this search to be deterministic (not dependendent
1193  * on order of processing through hash table), so as to avoid
1194  * flicker to to different decisions made if search is different
1195  * while dragging the offset number in the UI.  So look for the
1196  * lower vertex number when there is a choice of where to start.
1197  *
1198  * Note that this might not process all BevVerts, only the ones
1199  * that need adjustment.
1200  */
1201 static void adjust_offsets(BevelParams *bp)
1202 {
1203         BevVert *bv, *searchbv, *bvother;
1204         int i, searchi;
1205         GHashIterator giter;
1206         EdgeHalf *e, *efirst, *eother;
1207         GSQueue *q;
1208
1209         BLI_assert(!bp->vertex_only);
1210         GHASH_ITER(giter, bp->vert_hash) {
1211                 bv = BLI_ghashIterator_getValue(&giter);
1212                 bv->visited = false;
1213         }
1214
1215         q = BLI_gsqueue_new((int)sizeof(BevVert *));
1216         /* the following loop terminates because at least one node is visited each time */
1217         for (;;) {
1218                 /* look for root of a connected component in search graph */
1219                 searchbv = NULL;
1220                 searchi = -1;
1221                 GHASH_ITER(giter, bp->vert_hash) {
1222                         bv = BLI_ghashIterator_getValue(&giter);
1223                         if (!bv->visited && any_edge_half_offset_changed(bv)) {
1224                                 i = BM_elem_index_get(bv->v);
1225                                 if (!searchbv || i < searchi) {
1226                                         searchbv = bv;
1227                                         searchi = i;
1228                                 }
1229                         }
1230                 }
1231                 if (searchbv == NULL)
1232                         break;
1233
1234                 BLI_gsqueue_push(q, &searchbv);
1235                 while (!BLI_gsqueue_is_empty(q)) {
1236                         BLI_gsqueue_pop(q, &bv);
1237                         /* If do this check, don't have to check for already-on-queue before push, below */
1238                         if (bv->visited)
1239                                 continue;
1240                         bv->visited = true;
1241                         build_boundary(bp, bv, false);
1242
1243                         e = efirst = &bv->edges[0];
1244                         do {
1245                                 eother = find_other_end_edge_half(bp, e, &bvother);
1246                                 if (eother && !bvother->visited && edge_half_offset_changed(e)) {
1247                                         BLI_gsqueue_push(q, &bvother);
1248                                 }
1249                         } while ((e = e->next) != efirst);
1250                 }
1251         }
1252         BLI_gsqueue_free(q);
1253 }
1254
1255 /*
1256  * Given that the boundary is built and the boundary BMVerts have been made,
1257  * calculate the positions of the interior mesh points for the M_ADJ pattern,
1258  * then make the BMVerts and the new faces. */
1259 static void bevel_build_rings(BMesh *bm, BevVert *bv)
1260 {
1261         int k, ring, i, n, ns, ns2, nn, odd;
1262         VMesh *vm = bv->vmesh;
1263         BoundVert *v, *vprev, *vnext;
1264         NewVert *nv, *nvprev, *nvnext;
1265         EdgeHalf *e1, *e2, *epipe;
1266         BMVert *bmv, *bmv1, *bmv2, *bmv3, *bmv4;
1267         BMFace *f, *f2, *f23;
1268         float co[3], coa[3], cob[3], midco[3];
1269         float va_pipe[3], vb_pipe[3];
1270
1271         n = vm->count;
1272         ns = vm->seg;
1273         ns2 = ns / 2;
1274         odd = (ns % 2) != 0;
1275         BLI_assert(n > 2 && ns > 1);
1276
1277         /* special case: two beveled edges are in line and share a face, making a "pipe" */
1278         epipe = NULL;
1279         if (bv->selcount > 2) {
1280                 for (e1 = &bv->edges[0]; epipe == NULL && e1 != &bv->edges[bv->edgecount]; e1++) {
1281                         if (e1->is_bev) {
1282                                 for (e2 = &bv->edges[0]; e2 != &bv->edges[bv->edgecount]; e2++) {
1283                                         if (e1 != e2 && e2->is_bev) {
1284                                                 if ((e1->fnext == e2->fprev) || (e1->fprev == e2->fnext)) {
1285                                                         float dir1[3], dir2[3];
1286                                                         sub_v3_v3v3(dir1, bv->v->co, BM_edge_other_vert(e1->e, bv->v)->co);
1287                                                         sub_v3_v3v3(dir2, BM_edge_other_vert(e2->e, bv->v)->co, bv->v->co);
1288                                                         if (angle_v3v3(dir1, dir2) < 100.0f * BEVEL_EPSILON) {
1289                                                                 epipe = e1;
1290                                                                 break;
1291                                                         }
1292                                                 }
1293                                         }
1294                                 }
1295                         }
1296                 }
1297         }
1298
1299         /* Make initial rings, going between points on neighbors.
1300          * After this loop, will have coords for all (i, r, k) where
1301          * BoundVert for i has a bevel, 0 <= r <= ns2, 0 <= k <= ns */
1302         for (ring = 1; ring <= ns2; ring++) {
1303                 v = vm->boundstart;
1304
1305                 do {
1306                         i = v->index;
1307                         if (v->ebev) {
1308                                 /* get points coords of points a and b, on outer rings
1309                                  * of prev and next edges, k away from this edge */
1310                                 vprev = v->prev;
1311                                 vnext = v->next;
1312
1313                                 if (vprev->ebev)
1314                                         nvprev = mesh_vert(vm, vprev->index, 0, ns - ring);
1315                                 else
1316                                         nvprev = mesh_vert(vm, vprev->index, 0, ns);
1317                                 copy_v3_v3(coa, nvprev->co);
1318                                 nv = mesh_vert(vm, i, ring, 0);
1319                                 copy_v3_v3(nv->co, coa);
1320                                 nv->v = nvprev->v;
1321
1322                                 if (vnext->ebev)
1323                                         nvnext = mesh_vert(vm, vnext->index, 0, ring);
1324                                 else
1325                                         nvnext = mesh_vert(vm, vnext->index, 0, 0);
1326                                 copy_v3_v3(cob, nvnext->co);
1327                                 nv = mesh_vert(vm, i, ring, ns);
1328                                 copy_v3_v3(nv->co, cob);
1329                                 nv->v = nvnext->v;
1330
1331                                 /* TODO: better calculation of new midarc point? */
1332                                 project_to_edge(v->ebev->e, coa, cob, midco);
1333
1334                                 for (k = 1; k < ns; k++) {
1335                                         get_point_on_round_edge(v->ebev, k, coa, midco, cob, co);
1336                                         copy_v3_v3(mesh_vert(vm, i, ring, k)->co, co);
1337                                 }
1338
1339                                 if (v->ebev == epipe) {
1340                                         /* save profile extremes for later snapping */
1341                                         copy_v3_v3(va_pipe, mesh_vert(vm, i, 0, 0)->co);
1342                                         copy_v3_v3(vb_pipe, mesh_vert(vm, i, 0, ns)->co);
1343                                 }
1344                         }
1345                 } while ((v = v->next) != vm->boundstart);
1346         }
1347
1348         /* Now make sure cross points of rings share coordinates and vertices.
1349          * After this loop, will have BMVerts for all (i, r, k) where
1350          * i is for a BoundVert that is beveled and has either a predecessor or
1351          * successor BoundVert beveled too, and
1352          * for odd ns: 0 <= r <= ns2, 0 <= k <= ns
1353          * for even ns: 0 <= r < ns2, 0 <= k <= ns except k=ns2 */
1354         v = vm->boundstart;
1355         do {
1356                 i = v->index;
1357                 if (v->ebev) {
1358                         vprev = v->prev;
1359                         vnext = v->next;
1360                         if (vprev->ebev) {
1361                                 for (ring = 1; ring <= ns2; ring++) {
1362                                         for (k = 1; k <= ns2; k++) {
1363                                                 if (!odd && (k == ns2 || ring == ns2))
1364                                                         continue;  /* center line is special case: do after the rest are done */
1365                                                 nv = mesh_vert(vm, i, ring, k);
1366                                                 nvprev = mesh_vert(vm, vprev->index, k, ns - ring);
1367                                                 mid_v3_v3v3(co, nv->co, nvprev->co);
1368                                                 if (epipe)
1369                                                         snap_to_edge_profile(epipe, va_pipe, vb_pipe, co);
1370
1371                                                 copy_v3_v3(nv->co, co);
1372                                                 BLI_assert(nv->v == NULL && nvprev->v == NULL);
1373                                                 create_mesh_bmvert(bm, vm, i, ring, k, bv->v);
1374                                                 copy_mesh_vert(vm, vprev->index, k, ns - ring, i, ring, k);
1375                                         }
1376                                 }
1377                                 if (!vprev->prev->ebev) {
1378                                         for (ring = 1; ring <= ns2; ring++) {
1379                                                 for (k = 1; k <= ns2; k++) {
1380                                                         if (!odd && (k == ns2 || ring == ns2))
1381                                                                 continue;
1382                                                         create_mesh_bmvert(bm, vm, vprev->index, ring, k, bv->v);
1383                                                 }
1384                                         }
1385                                 }
1386                                 if (!vnext->ebev) {
1387                                         for (ring = 1; ring <= ns2; ring++) {
1388                                                 for (k = ns - ns2; k < ns; k++) {
1389                                                         if (!odd && (k == ns2 || ring == ns2))
1390                                                                 continue;
1391                                                         create_mesh_bmvert(bm, vm, i, ring, k, bv->v);
1392                                                 }
1393                                         }
1394                                 }
1395                         }
1396                 }
1397         } while ((v = v->next) != vm->boundstart);
1398
1399         if (!odd) {
1400                 /* Do special case center lines.
1401                  * This loop makes verts for (i, ns2, k) for 1 <= k <= ns-1, k!=ns2
1402                  * and for (i, r, ns2) for 1 <= r <= ns2-1,
1403                  * whenever i is in a sequence of at least two beveled verts */
1404                 v = vm->boundstart;
1405                 do {
1406                         i = v->index;
1407                         if (v->ebev) {
1408                                 vprev = v->prev;
1409                                 vnext = v->next;
1410                                 for (k = 1; k < ns2; k++) {
1411                                         nv = mesh_vert(vm, i, k, ns2);
1412                                         if (vprev->ebev)
1413                                                 nvprev = mesh_vert(vm, vprev->index, ns2, ns - k);
1414                                         if (vnext->ebev)
1415                                                 nvnext = mesh_vert(vm, vnext->index, ns2, k);
1416                                         if (vprev->ebev && vnext->ebev) {
1417                                                 mid_v3_v3v3v3(co, nvprev->co, nv->co, nvnext->co);
1418                                                 if (epipe)
1419                                                         snap_to_edge_profile(epipe, va_pipe, vb_pipe, co);
1420                                                 copy_v3_v3(nv->co, co);
1421                                                 create_mesh_bmvert(bm, vm, i, k, ns2, bv->v);
1422                                                 copy_mesh_vert(vm, vprev->index, ns2, ns - k, i, k, ns2);
1423                                                 copy_mesh_vert(vm, vnext->index, ns2, k, i, k, ns2);
1424
1425                                         }
1426                                         else if (vprev->ebev) {
1427                                                 mid_v3_v3v3(co, nvprev->co, nv->co);
1428                                                 if (epipe)
1429                                                         snap_to_edge_profile(epipe, va_pipe, vb_pipe, co);
1430                                                 copy_v3_v3(nv->co, co);
1431                                                 create_mesh_bmvert(bm, vm, i, k, ns2, bv->v);
1432                                                 copy_mesh_vert(vm, vprev->index, ns2, ns - k, i, k, ns2);
1433
1434                                                 create_mesh_bmvert(bm, vm, i, ns2, ns - k, bv->v);
1435                                         }
1436                                         else if (vnext->ebev) {
1437                                                 mid_v3_v3v3(co, nv->co, nvnext->co);
1438                                                 if (epipe)
1439                                                         snap_to_edge_profile(epipe, va_pipe, vb_pipe, co);
1440                                                 copy_v3_v3(nv->co, co);
1441                                                 create_mesh_bmvert(bm, vm, i, k, ns2, bv->v);
1442                                                 copy_mesh_vert(vm, vnext->index, ns2, k, i, k, ns2);
1443
1444                                                 create_mesh_bmvert(bm, vm, i, ns2, k, bv->v);
1445                                         }
1446                                 }
1447                         }
1448                 } while ((v = v->next) != vm->boundstart);
1449
1450                 /* center point need to be average of all centers of rings */
1451                 /* TODO: this is wrong if not all verts have ebev: could have
1452                  * several disconnected sections of mesh. */
1453                 zero_v3(midco);
1454                 nn = 0;
1455                 v = vm->boundstart;
1456                 do {
1457                         i = v->index;
1458                         if (v->ebev) {
1459                                 nv = mesh_vert(vm, i, ns2, ns2);
1460                                 add_v3_v3(midco, nv->co);
1461                                 nn++;
1462                         }
1463                 } while ((v = v->next) != vm->boundstart);
1464                 mul_v3_fl(midco, 1.0f / nn);
1465                 if (epipe)
1466                         snap_to_edge_profile(epipe, va_pipe, vb_pipe, midco);
1467                 bmv = BM_vert_create(bm, midco, NULL, BM_CREATE_NOP);
1468                 v = vm->boundstart;
1469                 do {
1470                         i = v->index;
1471                         if (v->ebev) {
1472                                 nv = mesh_vert(vm, i, ns2, ns2);
1473                                 copy_v3_v3(nv->co, midco);
1474                                 nv->v = bmv;
1475                         }
1476                 } while ((v = v->next) != vm->boundstart);
1477         }
1478
1479         /* Make the ring quads */
1480         for (ring = 0; ring < ns2; ring++) {
1481                 v = vm->boundstart;
1482                 do {
1483                         i = v->index;
1484                         f = boundvert_rep_face(v);
1485                         f2 = boundvert_rep_face(v->next);
1486                         if (v->ebev && (v->prev->ebev || v->next->ebev)) {
1487                                 for (k = 0; k < ns2 + odd; k++) {
1488                                         bmv1 = mesh_vert(vm, i, ring, k)->v;
1489                                         bmv2 = mesh_vert(vm, i, ring, k + 1)->v;
1490                                         bmv3 = mesh_vert(vm, i, ring + 1, k + 1)->v;
1491                                         bmv4 = mesh_vert(vm, i, ring + 1, k)->v;
1492                                         BLI_assert(bmv1 && bmv2 && bmv3 && bmv4);
1493                                         if (bmv3 == bmv4 || bmv1 == bmv4)
1494                                                 bmv4 = NULL;
1495                                         /* f23 is interp face for bmv2 and bmv3 */
1496                                         f23 = f;
1497                                         if (odd && k == ns2 && f2 && !v->any_seam)
1498                                                 f23 = f2;
1499                                         bev_create_quad_tri_ex(bm, bmv1, bmv2, bmv3, bmv4,
1500                                                                f, f23, f23, f);
1501                                 }
1502                         }
1503                         else if (v->prev->ebev && v->prev->prev->ebev) {
1504                                 /* finish off a sequence of beveled edges */
1505                                 i = v->prev->index;
1506                                 f = boundvert_rep_face(v->prev);
1507                                 f2 = boundvert_rep_face(v);
1508                                 for (k = ns2 + (ns % 2); k < ns; k++) {
1509                                         bmv1 = mesh_vert(vm, i, ring, k)->v;
1510                                         bmv2 = mesh_vert(vm, i, ring, k + 1)->v;
1511                                         bmv3 = mesh_vert(vm, i, ring + 1, k + 1)->v;
1512                                         bmv4 = mesh_vert(vm, i, ring + 1, k)->v;
1513                                         BLI_assert(bmv1 && bmv2 && bmv3 && bmv4);
1514                                         if (bmv2 == bmv3) {
1515                                                 bmv3 = bmv4;
1516                                                 bmv4 = NULL;
1517                                         }
1518                                         f23 = f;
1519                                         if (odd && k == ns2 && f2 && !v->any_seam)
1520                                                 f23 = f2;
1521                                         bev_create_quad_tri_ex(bm, bmv1, bmv2, bmv3, bmv4,
1522                                                                f, f23, f23, f);
1523                                 }
1524                         }
1525                 } while ((v = v->next) != vm->boundstart);
1526         }
1527
1528         /* Fix UVs along center lines if even number of segments */
1529         if (!odd) {
1530                 v = vm->boundstart;
1531                 do {
1532                         i = v->index;
1533                         f = boundvert_rep_face(v);
1534                         f2 = boundvert_rep_face(v->next);
1535                         if (!v->any_seam) {
1536                                 for (ring = 1; ring < ns2; ring++) {
1537                                         BMVert *v_uv = mesh_vert(vm, i, ring, ns2)->v;
1538                                         if (v_uv) {
1539                                                 bev_merge_uvs(bm, v_uv);
1540                                         }
1541                                 }
1542                         }
1543                 } while ((v = v->next) != vm->boundstart);
1544                 if (!bv->any_seam)
1545                         bev_merge_uvs(bm, mesh_vert(vm, 0, ns2, ns2)->v);
1546         }
1547
1548         /* Make center ngon if odd number of segments and fully beveled */
1549         if (odd && vm->count == bv->selcount) {
1550                 BMVert **vv = NULL;
1551                 BMFace **vf = NULL;
1552                 BLI_array_staticdeclare(vv, BM_DEFAULT_NGON_STACK_SIZE);
1553                 BLI_array_staticdeclare(vf, BM_DEFAULT_NGON_STACK_SIZE);
1554
1555                 v = vm->boundstart;
1556                 do {
1557                         i = v->index;
1558                         BLI_assert(v->ebev);
1559                         BLI_array_append(vv, mesh_vert(vm, i, ns2, ns2)->v);
1560                         BLI_array_append(vf, bv->any_seam ? f: boundvert_rep_face(v));
1561                 } while ((v = v->next) != vm->boundstart);
1562                 f = boundvert_rep_face(vm->boundstart);
1563                 bev_create_ngon(bm, vv, BLI_array_count(vv), vf, f, true);
1564
1565                 BLI_array_free(vv);
1566         }
1567
1568         /* Make 'rest-of-vmesh' polygon if not fully beveled */
1569         /* TODO: use interpolation face array here too */
1570         if (vm->count > bv->selcount) {
1571                 int j;
1572                 BMVert **vv = NULL;
1573                 BLI_array_staticdeclare(vv, BM_DEFAULT_NGON_STACK_SIZE);
1574
1575                 v = vm->boundstart;
1576                 f = boundvert_rep_face(v);
1577                 j = 0;
1578                 do {
1579                         i = v->index;
1580                         if (v->ebev) {
1581                                 if (!v->prev->ebev) {
1582                                         for (k = 0; k < ns2; k++) {
1583                                                 bmv1 = mesh_vert(vm, i, ns2, k)->v;
1584                                                 if (!bmv1)
1585                                                         bmv1 = mesh_vert(vm, i, 0, k)->v;
1586                                                 if (!(j > 0 && bmv1 == vv[j - 1])) {
1587                                                         BLI_assert(bmv1 != NULL);
1588                                                         BLI_array_append(vv, bmv1);
1589                                                         j++;
1590                                                 }
1591                                         }
1592                                 }
1593                                 bmv1 = mesh_vert(vm, i, ns2, ns2)->v;
1594                                 if (!bmv1)
1595                                         bmv1 = mesh_vert(vm, i, 0, ns2)->v;
1596                                 if (!(j > 0 && bmv1 == vv[j - 1])) {
1597                                         BLI_assert(bmv1 != NULL);
1598                                         BLI_array_append(vv, bmv1);
1599                                         j++;
1600                                 }
1601                                 if (!v->next->ebev) {
1602                                         for (k = ns - ns2; k < ns; k++) {
1603                                                 bmv1 = mesh_vert(vm, i, ns2, k)->v;
1604                                                 if (!bmv1)
1605                                                         bmv1 = mesh_vert(vm, i, 0, k)->v;
1606                                                 if (!(j > 0 && bmv1 == vv[j - 1])) {
1607                                                         BLI_assert(bmv1 != NULL);
1608                                                         BLI_array_append(vv, bmv1);
1609                                                         j++;
1610                                                 }
1611                                         }
1612                                 }
1613                         }
1614                         else {
1615                                 BLI_assert(mesh_vert(vm, i, 0, 0)->v != NULL);
1616                                 BLI_array_append(vv, mesh_vert(vm, i, 0, 0)->v);
1617                                 j++;
1618                         }
1619                 } while ((v = v->next) != vm->boundstart);
1620                 if (vv[0] == vv[j - 1])
1621                         j--;
1622                 bev_create_ngon(bm, vv, j, NULL, f, true);
1623
1624                 BLI_array_free(vv);
1625         }
1626 }
1627
1628 static VMesh *new_adj_subdiv_vmesh(MemArena *mem_arena, int count, int seg, BoundVert *bounds)
1629 {
1630         VMesh *vm;
1631
1632         vm = (VMesh *)BLI_memarena_alloc(mem_arena, sizeof(VMesh));
1633         vm->count = count;
1634         vm->seg = seg;
1635         vm->boundstart = bounds;
1636         vm->mesh = (NewVert *)BLI_memarena_alloc(mem_arena, count * (1 + seg / 2) * (1 + seg) * sizeof(NewVert));
1637         vm->mesh_kind = M_ADJ_SUBDIV;
1638         return vm;
1639 }
1640
1641 /* VMesh verts for vertex i have data for (i, 0 <= j <= ns2, 0 <= k <= ns), where ns2 = floor(nseg / 2).
1642  * But these overlap data from previous and next i: there are some forced equivalences.
1643  * Let's call these indices the canonical ones: we will just calculate data for these
1644  *    0 <= j <= ns2, 0 <= k < ns2  (for odd ns2)
1645  *    0 <= j < ns2, 0 <= k <= ns2  (for even ns2)
1646  *        also (j=ns2, k=ns2) at i=0 (for even ns2)
1647  * This function returns the canonical one for any i, j, k in [0,n],[0,ns],[0,ns] */
1648 static NewVert *mesh_vert_canon(VMesh *vm, int i, int j, int k)
1649 {
1650         int n, ns, ns2, odd;
1651         NewVert *ans;
1652
1653         n = vm->count;
1654         ns = vm->seg;
1655         ns2 = ns / 2;
1656         odd = ns % 2;
1657         BLI_assert(0 <= i && i <= n && 0 <= j && j <= ns && 0 <= k && k <= ns);
1658
1659         if (!odd && j == ns2 && k == ns2)
1660                 ans = mesh_vert(vm, 0, j, k);
1661         else if (j <= ns2 - 1 + odd && k <= ns2)
1662                 ans = mesh_vert(vm, i, j, k);
1663         else if (k <= ns2)
1664                 ans = mesh_vert(vm, (i + n - 1) % n, k, ns - j);
1665         else
1666                 ans = mesh_vert(vm, (i + 1) % n, ns - k, j);
1667         return ans;
1668 }
1669
1670 static int is_canon(VMesh *vm, int i, int j, int k)
1671 {
1672         int ns2 = vm->seg / 2;
1673         if (vm->seg % 2 == 1)
1674                 return (j <= ns2 && k <= ns2);
1675         else
1676                 return ((j < ns2 && k <= ns2) || (j == ns2 && k == ns2 && i == 0));
1677 }
1678
1679 /* Copy the vertex data to all of vm verts from canonical ones */
1680 static void vmesh_copy_equiv_verts(VMesh *vm)
1681 {
1682         int n, ns, ns2, i, j, k;
1683         NewVert *v0, *v1;
1684
1685         n = vm->count;
1686         ns = vm->seg;
1687         ns2 = ns / 2;
1688         for (i = 0; i < n; i++) {
1689                 for (j = 0; j <= ns2; j++) {
1690                         for (k = 0; k <= ns; k++) {
1691                                 if (is_canon(vm, i, j, k))
1692                                         continue;
1693                                 v1 = mesh_vert(vm, i, j, k);
1694                                 v0 = mesh_vert_canon(vm, i, j, k);
1695                                 copy_v3_v3(v1->co, v0->co);
1696                                 v1->v = v0->v;
1697                         }
1698                 }
1699         }
1700 }
1701
1702 /* Calculate and return in r_cent the centroid of the center poly */
1703 static void vmesh_center(VMesh *vm, float r_cent[3])
1704 {
1705         int n, ns2, i;
1706
1707         n = vm->count;
1708         ns2 = vm->seg / 2;
1709         if (vm->seg % 2) {
1710                 zero_v3(r_cent);
1711                 for (i = 0; i < n; i++) {
1712                         add_v3_v3(r_cent, mesh_vert(vm, i, ns2, ns2)->co);
1713                 }
1714                 mul_v3_fl(r_cent, 1.0f / (float) n);
1715         }
1716         else {
1717                 copy_v3_v3(r_cent, mesh_vert(vm, 0, ns2, ns2)->co);
1718         }
1719 }
1720
1721 /* Do one step of quadratic subdivision (Doo-Sabin), with special rules at boundaries.
1722  * For now, this is written assuming vm0->nseg is odd.
1723  * See Hwang-Chuang 2003 paper: "N-sided hole filling and vertex blending using subdivision surfaces"  */
1724 static VMesh *quadratic_subdiv(MemArena *mem_arena, VMesh *vm0)
1725 {
1726         int n, ns0, ns20, ns1 /*, ns21 */;
1727         int i, j, k, j1, k1;
1728         VMesh *vm1;
1729         float co[3], co1[3], co2[3], co3[3], co4[3];
1730         float co11[3], co21[3], co31[3], co41[3];
1731         float denom;
1732         const float wcorner[4] = {0.25f, 0.25f, 0.25f, 0.25f};
1733         const float wboundary[4] = {0.375f, 0.375f, 0.125f, 0.125f};  /* {3, 3, 1, 1}/8 */
1734         const float winterior[4] = {0.5625f, 0.1875f, 0.1875f, 0.0625f}; /* {9, 3, 3, 1}/16 */
1735
1736         n = vm0->count;
1737         ns0 = vm0->seg;
1738         ns20 = ns0 / 2;
1739         BLI_assert(ns0 % 2 == 1);
1740
1741         ns1 = 2 * ns0 - 1;
1742         // ns21 = ns1 / 2;  /* UNUSED */
1743         vm1 = new_adj_subdiv_vmesh(mem_arena, n, ns1, vm0->boundstart);
1744
1745         for (i = 0; i < n; i ++) {
1746                 /* For handle vm0 polys with lower left corner at (i,j,k) for
1747                  * j in [0, ns20], k in [0, ns20]; then the center ngon.
1748                  * but only fill in data for canonical verts of v1. */
1749                 for (j = 0; j <= ns20; j++) {
1750                         for (k = 0; k <= ns20; k++) {
1751                                 if (j == ns20 && k == ns20)
1752                                         continue;  /* center ngon is special */
1753                                 copy_v3_v3(co1, mesh_vert_canon(vm0, i, j, k)->co);
1754                                 copy_v3_v3(co2, mesh_vert_canon(vm0, i, j, k + 1)->co);
1755                                 copy_v3_v3(co3, mesh_vert_canon(vm0, i, j + 1, k + 1)->co);
1756                                 copy_v3_v3(co4, mesh_vert_canon(vm0, i, j + 1, k)->co);
1757                                 if (j == 0 && k == 0) {
1758                                         /* corner */
1759                                         copy_v3_v3(co11, co1);
1760                                         interp_v3_v3v3(co21, co1, co2, 0.5f);
1761                                         interp_v3_v3v3v3v3(co31, co1, co2, co3, co4, wcorner);
1762                                         interp_v3_v3v3(co41, co1, co4, 0.5f);
1763                                 }
1764                                 else if (j == 0) {
1765                                         /* ring 0 boundary */
1766                                         interp_v3_v3v3(co11, co1, co2, 0.25f);
1767                                         interp_v3_v3v3(co21, co1, co2, 0.75f);
1768                                         interp_v3_v3v3v3v3(co31, co2, co3, co1, co4, wboundary);
1769                                         interp_v3_v3v3v3v3(co41, co1, co4, co2, co3, wboundary);
1770                                 }
1771                                 else if (k == 0) {
1772                                         /* ring-starts boundary */
1773                                         interp_v3_v3v3(co11, co1, co4, 0.25f);
1774                                         interp_v3_v3v3v3v3(co21, co1, co2, co3, co4, wboundary);
1775                                         interp_v3_v3v3v3v3(co31, co3, co4, co1, co2, wboundary);
1776                                         interp_v3_v3v3(co41, co1, co4, 0.75f);
1777                                 }
1778                                 else {
1779                                         /* interior */
1780                                         interp_v3_v3v3v3v3(co11, co1, co2, co4, co3, winterior);
1781                                         interp_v3_v3v3v3v3(co21, co2, co1, co3, co4, winterior);
1782                                         interp_v3_v3v3v3v3(co31, co3, co2, co4, co1, winterior);
1783                                         interp_v3_v3v3v3v3(co41, co4, co1, co3, co2, winterior);
1784                                 }
1785                                 j1 = 2 * j;
1786                                 k1 = 2 * k;
1787                                 if (is_canon(vm1, i, j1, k1))
1788                                         copy_v3_v3(mesh_vert(vm1, i, j1, k1)->co, co11);
1789                                 if (is_canon(vm1, i, j1, k1 + 1))
1790                                         copy_v3_v3(mesh_vert(vm1, i, j1, k1 + 1)->co, co21);
1791                                 if (is_canon(vm1, i, j1 + 1, k1 + 1))
1792                                         copy_v3_v3(mesh_vert(vm1, i, j1 + 1, k1 + 1)->co, co31);
1793                                 if (is_canon(vm1, i, j1 + 1, k1))
1794                                         copy_v3_v3(mesh_vert(vm1, i, j1 + 1, k1)->co, co41);
1795                         }
1796                 }
1797
1798                 /* center ngon */
1799                 denom = 8.0f * (float) n;
1800                 zero_v3(co);
1801                 for (j = 0; j < n; j++) {
1802                         copy_v3_v3(co1, mesh_vert(vm0, j, ns20, ns20)->co);
1803                         if (i == j)
1804                                 madd_v3_v3fl(co, co1, (4.0f * (float) n + 2.0f) / denom);
1805                         else if ((i + 1) % n == j || (i + n - 1) % n == j)
1806                                 madd_v3_v3fl(co, co1, ((float) n + 2.0f) / denom);
1807                         else
1808                                 madd_v3_v3fl(co, co1, 2.0f / denom);
1809                 }
1810                 copy_v3_v3(mesh_vert(vm1, i, 2 * ns20, 2 * ns20)->co, co);
1811         }
1812
1813         vmesh_copy_equiv_verts(vm1);
1814         return vm1;
1815 }
1816
1817 /* After a step of quadratic_subdiv, adjust the ring 1 verts to be on the planes of their respective faces,
1818  * so that the cross-tangents will match on further subdivision. */
1819 static void fix_vmesh_tangents(VMesh *vm, BevVert *bv)
1820 {
1821         int i, n;
1822         NewVert *v;
1823         BoundVert *bndv;
1824         float co[3];
1825
1826         n = vm->count;
1827         bndv = vm->boundstart;
1828         do {
1829                 i = bndv->index;
1830
1831                 /* (i, 1, 1) snap to edge line */
1832                 v = mesh_vert(vm, i, 1, 1);
1833                 closest_to_line_v3(co, v->co, bndv->nv.co, bv->v->co);
1834                 copy_v3_v3(v->co, co);
1835                 copy_v3_v3(mesh_vert(vm, (i + n -1) % n, 1, vm->seg - 1)->co, co);
1836
1837                 /* Also want (i, 1, k) snapped to plane of adjacent face for
1838                  * 1 < k < ns - 1, but current initial cage and subdiv rules
1839                  * ensure this, so nothing to do */
1840         } while ((bndv = bndv->next) != vm->boundstart);
1841 }
1842
1843 /* Fill frac with fractions of way along ring 0 for vertex i, for use with interp_range function */
1844 static void fill_vmesh_fracs(VMesh *vm, float *frac, int i)
1845 {
1846         int k, ns;
1847         float total = 0.0f;
1848
1849         ns = vm->seg;
1850         frac[0] = 0.0f;
1851         for (k = 0; k < ns; k++) {
1852                 total += len_v3v3(mesh_vert(vm, i, 0, k)->co, mesh_vert(vm, i, 0, k + 1)->co);
1853                 frac[k + 1] = total;
1854         }
1855         if (total > BEVEL_EPSILON) {
1856                 for (k = 1; k <= ns; k++)
1857                         frac[k] /= total;
1858         }
1859 }
1860
1861 /* Return i such that frac[i] <= f <= frac[i + 1], where frac[n] == 1.0
1862  * and put fraction of rest of way between frac[i] and frac[i + 1] into r_rest */
1863 static int interp_range(const float *frac, int n, const float f, float *r_rest)
1864 {
1865         int i;
1866         float rest;
1867
1868         /* could binary search in frac, but expect n to be reasonably small */
1869         for (i = 0; i < n; i++) {
1870                 if (f <= frac[i + 1]) {
1871                         rest = f - frac[i];
1872                         if (rest == 0)
1873                                 *r_rest = 0.0f;
1874                         else
1875                                 *r_rest = rest / (frac[i + 1] - frac[i]);
1876                         return i;
1877                 }
1878         }
1879         *r_rest = 0.0f;
1880         return n;
1881 }
1882
1883 /* Interpolate given vmesh to make one with target nseg and evenly spaced border vertices */
1884 static VMesh *interp_vmesh(MemArena *mem_arena, VMesh *vm0, int nseg)
1885 {
1886         int n, ns0, nseg2, odd, i, j, k, j0, k0;
1887         float *prev_frac, *frac, f, restj, restk;
1888         float quad[4][3], co[3], center[3];
1889         VMesh *vm1;
1890
1891         n = vm0->count;
1892         ns0 = vm0->seg;
1893         nseg2 = nseg / 2;
1894         odd = nseg % 2;
1895         vm1 = new_adj_subdiv_vmesh(mem_arena, n, nseg, vm0->boundstart);
1896         prev_frac = (float *)BLI_memarena_alloc(mem_arena, (ns0 + 1 ) *sizeof(float));
1897         frac = (float *)BLI_memarena_alloc(mem_arena, (ns0 + 1 ) *sizeof(float));
1898
1899         fill_vmesh_fracs(vm0, prev_frac, n - 1);
1900         fill_vmesh_fracs(vm0, frac, 0);
1901         for (i = 0; i < n; i++) {
1902                 for (j = 0; j <= nseg2 -1 + odd; j++) {
1903                         for (k = 0; k <= nseg2; k++) {
1904                                 f = (float) k / (float) nseg;
1905                                 k0 = interp_range(frac, ns0, f, &restk);
1906                                 f = 1.0f - (float) j / (float) nseg;
1907                                 j0 = interp_range(prev_frac, ns0, f, &restj);
1908                                 if (restj < BEVEL_EPSILON) {
1909                                         j0 = ns0 - j0;
1910                                         restj = 0.0f;
1911                                 }
1912                                 else {
1913                                         j0 = ns0 - j0 - 1;
1914                                         restj = 1.0f - restj;
1915                                 }
1916                                 /* Use bilinear interpolation within the source quad; could be smarter here */
1917                                 if (restj < BEVEL_EPSILON && restk < BEVEL_EPSILON) {
1918                                         copy_v3_v3(co, mesh_vert_canon(vm0, i, j0, k0)->co);
1919                                 }
1920                                 else {
1921                                         copy_v3_v3(quad[0], mesh_vert_canon(vm0, i, j0, k0)->co);
1922                                         copy_v3_v3(quad[1], mesh_vert_canon(vm0, i, j0, k0 + 1)->co);
1923                                         copy_v3_v3(quad[2], mesh_vert_canon(vm0, i, j0 + 1, k0 + 1)->co);
1924                                         copy_v3_v3(quad[3], mesh_vert_canon(vm0, i, j0 + 1, k0)->co);
1925                                         interp_bilinear_quad_v3(quad, restk, restj, co);
1926                                 }
1927                                 copy_v3_v3(mesh_vert(vm1, i, j, k)->co, co);
1928                         }
1929                 }
1930         }
1931         if (!odd) {
1932                 vmesh_center(vm0, center);
1933                 copy_v3_v3(mesh_vert(vm1, 0, nseg2, nseg2)->co, center);
1934         }
1935         vmesh_copy_equiv_verts(vm1);
1936         return vm1;
1937 }
1938
1939 /*
1940  * Given that the boundary is built and the boundary BMVerts have been made,
1941  * calculate the positions of the interior mesh points for the M_ADJ_SUBDIV pattern,
1942  * then make the BMVerts and the new faces. */
1943 static void bevel_build_rings_subdiv(BevelParams *bp, BMesh *bm, BevVert *bv)
1944 {
1945         int n, ns, ns2, odd, i, j, k;
1946         VMesh *vm0, *vm1, *vm;
1947         float coa[3], cob[3], coc[3];
1948         BoundVert *v;
1949         BMVert *bmv1, *bmv2, *bmv3, *bmv4;
1950         BMFace *f, *f2, *f23;
1951         MemArena *mem_arena = bp->mem_arena;
1952         const float fullness = 0.5f;
1953
1954         n = bv->edgecount;
1955         ns = bv->vmesh->seg;
1956         ns2 = ns / 2;
1957         odd = ns % 2;
1958         BLI_assert(n >= 3 && ns > 1);
1959
1960         /* First construct an initial control mesh, with nseg==3 */
1961         vm0 = new_adj_subdiv_vmesh(mem_arena, n, 3, bv->vmesh->boundstart);
1962
1963         for (i = 0; i < n; i++) {
1964                 /* Boundaries just divide input polygon edges into 3 even segments */
1965                 copy_v3_v3(coa, mesh_vert(bv->vmesh, i, 0, 0)->co);
1966                 copy_v3_v3(cob, mesh_vert(bv->vmesh, (i + 1) % n, 0, 0)->co);
1967                 copy_v3_v3(coc, mesh_vert(bv->vmesh, (i + n -1) % n, 0, 0)->co);
1968                 copy_v3_v3(mesh_vert(vm0, i, 0, 0)->co, coa);
1969                 interp_v3_v3v3(mesh_vert(vm0, i, 0, 1)->co, coa, cob, 1.0f / 3.0f);
1970                 interp_v3_v3v3(mesh_vert(vm0, i, 1, 0)->co, coa, coc, 1.0f / 3.0f);
1971                 interp_v3_v3v3(mesh_vert(vm0, i, 1, 1)->co, coa, bv->v->co, fullness);
1972         }
1973         vmesh_copy_equiv_verts(vm0);
1974
1975         vm1 = vm0;
1976         do {
1977                 vm1 = quadratic_subdiv(mem_arena, vm1);
1978                 fix_vmesh_tangents(vm1, bv);
1979         } while (vm1->seg <= ns);
1980         vm1 = interp_vmesh(mem_arena, vm1, ns);
1981
1982         /* copy final vmesh into bv->vmesh, make BMVerts and BMFaces */
1983         vm = bv->vmesh;
1984         for (i = 0; i < n; i ++) {
1985                 for (j = 0; j <= ns2; j++) {
1986                         for (k = 0; k <= ns; k++) {
1987                                 if (j == 0 && (k == 0 || k == ns))
1988                                         continue;  /* boundary corners already made */
1989                                 if (!is_canon(vm, i, j, k))
1990                                         continue;
1991                                 copy_v3_v3(mesh_vert(vm, i, j, k)->co, mesh_vert(vm1, i, j, k)->co);
1992                                 create_mesh_bmvert(bm, vm, i, j, k, bv->v);
1993                         }
1994                 }
1995         }
1996         vmesh_copy_equiv_verts(vm);
1997         /* make the polygons */
1998         v = vm->boundstart;
1999         do {
2000                 i = v->index;
2001                 f = boundvert_rep_face(v);
2002                 f2 = boundvert_rep_face(v->next);
2003                 /* For odd ns, make polys with lower left corner at (i,j,k) for
2004                  *    j in [0, ns2-1], k in [0, ns2].  And then the center ngon.
2005                  * For even ns,
2006                  *    j in [0, ns2-1], k in [0, ns2-1] */
2007                 for (j = 0; j < ns2; j++) {
2008                         for (k = 0; k < ns2 + odd; k++) {
2009                                 bmv1 = mesh_vert(vm, i, j, k)->v;
2010                                 bmv2 = mesh_vert(vm, i, j, k + 1)->v;
2011                                 bmv3 = mesh_vert(vm, i, j + 1, k + 1)->v;
2012                                 bmv4 = mesh_vert(vm, i, j + 1, k)->v;
2013                                 BLI_assert(bmv1 && bmv2 && bmv3 && bmv4);
2014                                 f23 = f;
2015                                 if (odd && k == ns2 && f2 && !v->any_seam)
2016                                         f23 = f2;
2017                                 bev_create_quad_tri_ex(bm, bmv1, bmv2, bmv3, bmv4,
2018                                                        f, f23, f23, f);
2019                         }
2020                 }
2021         } while ((v = v->next) != vm->boundstart);
2022
2023         /* center ngon */
2024         if (odd) {
2025                 BMVert **vv = NULL;
2026                 BMFace **vf = NULL;
2027                 BLI_array_staticdeclare(vv, BM_DEFAULT_NGON_STACK_SIZE);
2028                 BLI_array_staticdeclare(vf, BM_DEFAULT_NGON_STACK_SIZE);
2029
2030                 v = vm->boundstart;
2031                 do {
2032                         i = v->index;
2033                         BLI_array_append(vv, mesh_vert(vm, i, ns2, ns2)->v);
2034                         BLI_array_append(vf, v->any_seam ? f : boundvert_rep_face(v));
2035                 } while ((v = v->next) != vm->boundstart);
2036                 f = boundvert_rep_face(vm->boundstart);
2037                 bev_create_ngon(bm, vv, BLI_array_count(vv), vf, f, true);
2038
2039                 BLI_array_free(vv);
2040         }
2041 }
2042
2043 static BMFace *bevel_build_poly(BMesh *bm, BevVert *bv)
2044 {
2045         BMFace *f;
2046         int n, k;
2047         VMesh *vm = bv->vmesh;
2048         BoundVert *v;
2049         BMFace *frep;
2050         BMVert **vv = NULL;
2051         BMFace **vf = NULL;
2052         BLI_array_staticdeclare(vv, BM_DEFAULT_NGON_STACK_SIZE);
2053         BLI_array_staticdeclare(vf, BM_DEFAULT_NGON_STACK_SIZE);
2054
2055         frep = boundvert_rep_face(vm->boundstart);
2056         v = vm->boundstart;
2057         n = 0;
2058         do {
2059                 /* accumulate vertices for vertex ngon */
2060                 /* also accumulate faces in which uv interpolation is to happen for each */
2061                 BLI_array_append(vv, v->nv.v);
2062                 BLI_array_append(vf, bv->any_seam ? frep : boundvert_rep_face(v));
2063                 n++;
2064                 if (v->ebev && v->ebev->seg > 1) {
2065                         for (k = 1; k < v->ebev->seg; k++) {
2066                                 BLI_array_append(vv, mesh_vert(vm, v->index, 0, k)->v);
2067                                 BLI_array_append(vf, bv->any_seam ? frep : boundvert_rep_face(v));
2068                                 n++;
2069                         }
2070                 }
2071         } while ((v = v->next) != vm->boundstart);
2072         if (n > 2) {
2073                 f = bev_create_ngon(bm, vv, n, vf, boundvert_rep_face(v), true);
2074         }
2075         else {
2076                 f = NULL;
2077         }
2078         BLI_array_free(vv);
2079         return f;
2080 }
2081
2082 static void bevel_build_trifan(BMesh *bm, BevVert *bv)
2083 {
2084         BMFace *f;
2085         BLI_assert(next_bev(bv, NULL)->seg == 1 || bv->selcount == 1);
2086
2087         f = bevel_build_poly(bm, bv);
2088
2089         if (f) {
2090                 /* we have a polygon which we know starts at the previous vertex, make it into a fan */
2091                 BMLoop *l_fan = BM_FACE_FIRST_LOOP(f)->prev;
2092                 BMVert *v_fan = l_fan->v;
2093
2094                 while (f->len > 3) {
2095                         BMLoop *l_new;
2096                         BMFace *f_new;
2097                         BLI_assert(v_fan == l_fan->v);
2098                         f_new = BM_face_split(bm, f, l_fan, l_fan->next->next, &l_new, NULL, FALSE);
2099
2100                         if (f_new->len > f->len) {
2101                                 f = f_new;
2102                                 if      (l_new->v       == v_fan) { l_fan = l_new; }
2103                                 else if (l_new->next->v == v_fan) { l_fan = l_new->next; }
2104                                 else if (l_new->prev->v == v_fan) { l_fan = l_new->prev; }
2105                                 else { BLI_assert(0); }
2106                         }
2107                         else {
2108                                 if      (l_fan->v       == v_fan) { /* l_fan = l_fan; */ }
2109                                 else if (l_fan->next->v == v_fan) { l_fan = l_fan->next; }
2110                                 else if (l_fan->prev->v == v_fan) { l_fan = l_fan->prev; }
2111                                 else { BLI_assert(0); }
2112                         }
2113                 }
2114         }
2115 }
2116
2117 static void bevel_build_quadstrip(BMesh *bm, BevVert *bv)
2118 {
2119         BMFace *f;
2120         BLI_assert(bv->selcount == 2);
2121
2122         f = bevel_build_poly(bm, bv);
2123
2124         if (f) {
2125                 /* we have a polygon which we know starts at this vertex, make it into strips */
2126                 EdgeHalf *eh_a = bv->vmesh->boundstart->elast;
2127                 EdgeHalf *eh_b = next_bev(bv, eh_a->next);  /* since (selcount == 2) we know this is valid */
2128                 BMLoop *l_a = BM_face_vert_share_loop(f, eh_a->rightv->nv.v);
2129                 BMLoop *l_b = BM_face_vert_share_loop(f, eh_b->leftv->nv.v);
2130                 int split_count = bv->vmesh->seg + 1;  /* ensure we don't walk past the segments */
2131
2132                 while (f->len > 4 && split_count > 0) {
2133                         BMLoop *l_new;
2134                         BLI_assert(l_a->f == f);
2135                         BLI_assert(l_b->f == f);
2136
2137                         if (l_a-> v == l_b->v || l_a->next == l_b) {
2138                                 /* l_a->v and l_b->v can be the same or such that we'd make a 2-vertex poly */
2139                                 l_a = l_a->prev;
2140                                 l_b = l_b->next;
2141                         }
2142                         else {
2143                                 BM_face_split(bm, f, l_a, l_b, &l_new, NULL, FALSE);
2144                                 f = l_new->f;
2145
2146                                 /* walk around the new face to get the next verts to split */
2147                                 l_a = l_new->prev;
2148                                 l_b = l_new->next->next;
2149                         }
2150                         split_count--;
2151                 }
2152         }
2153 }
2154
2155 /* Given that the boundary is built, now make the actual BMVerts
2156  * for the boundary and the interior of the vertex mesh. */
2157 static void build_vmesh(BevelParams *bp, BMesh *bm, BevVert *bv)
2158 {
2159         MemArena *mem_arena = bp->mem_arena;
2160         VMesh *vm = bv->vmesh;
2161         BoundVert *v, *weld1, *weld2;
2162         int n, ns, ns2, i, k, weld;
2163         float *va, *vb, co[3];
2164         float midco[3];
2165
2166         n = vm->count;
2167         ns = vm->seg;
2168         ns2 = ns / 2;
2169
2170         vm->mesh = (NewVert *)BLI_memarena_alloc(mem_arena, n * (ns2 + 1) * (ns + 1) * sizeof(NewVert));
2171
2172         /* special case: two beveled ends welded together */
2173         weld = (bv->selcount == 2) && (vm->count == 2);
2174         weld1 = weld2 = NULL;   /* will hold two BoundVerts involved in weld */
2175
2176         /* make (i, 0, 0) mesh verts for all i */
2177         v = vm->boundstart;
2178         do {
2179                 i = v->index;
2180                 copy_v3_v3(mesh_vert(vm, i, 0, 0)->co, v->nv.co);
2181                 create_mesh_bmvert(bm, vm, i, 0, 0, bv->v);
2182                 v->nv.v = mesh_vert(vm, i, 0, 0)->v;
2183                 if (weld && v->ebev) {
2184                         if (!weld1)
2185                                 weld1 = v;
2186                         else
2187                                 weld2 = v;
2188                 }
2189         } while ((v = v->next) != vm->boundstart);
2190
2191         /* copy other ends to (i, 0, ns) for all i, and fill in profiles for beveled edges */
2192         v = vm->boundstart;
2193         do {
2194                 i = v->index;
2195                 copy_mesh_vert(vm, i, 0, ns, v->next->index, 0, 0);
2196                 if (v->ebev) {
2197                         va = mesh_vert(vm, i, 0, 0)->co;
2198                         vb = mesh_vert(vm, i, 0, ns)->co;
2199                         if (bv->edgecount == 3 && bv->selcount == 1) {
2200                                 /* special case: profile cuts the third face, so line it up with that */
2201                                 copy_v3_v3(midco, bv->v->co);
2202                         }
2203                         else {
2204                                 project_to_edge(v->ebev->e, va, vb, midco);
2205                         }
2206                         for (k = 1; k < ns; k++) {
2207                                 get_point_on_round_edge(v->ebev, k, va, midco, vb, co);
2208                                 copy_v3_v3(mesh_vert(vm, i, 0, k)->co, co);
2209                                 if (!weld)
2210                                         create_mesh_bmvert(bm, vm, i, 0, k, bv->v);
2211                         }
2212                 }
2213         } while ((v = v->next) != vm->boundstart);
2214
2215         if (weld) {
2216                 vm->mesh_kind = M_NONE;
2217                 for (k = 1; k < ns; k++) {
2218                         va = mesh_vert(vm, weld1->index, 0, k)->co;
2219                         vb = mesh_vert(vm, weld2->index, 0, ns - k)->co;
2220                         mid_v3_v3v3(co, va, vb);
2221                         copy_v3_v3(mesh_vert(vm, weld1->index, 0, k)->co, co);
2222                         create_mesh_bmvert(bm, vm, weld1->index, 0, k, bv->v);
2223                 }
2224                 for (k = 1; k < ns; k++)
2225                         copy_mesh_vert(vm, weld2->index, 0, ns - k, weld1->index, 0, k);
2226         }
2227
2228         switch (vm->mesh_kind) {
2229                 case M_NONE:
2230                         /* do nothing */
2231                         break;
2232                 case M_POLY:
2233                         bevel_build_poly(bm, bv);
2234                         break;
2235                 case M_ADJ:
2236                         bevel_build_rings(bm, bv);
2237                         break;
2238                 case M_ADJ_SUBDIV:
2239                         bevel_build_rings_subdiv(bp, bm, bv);
2240                         break;
2241                 case M_TRI_FAN:
2242                         bevel_build_trifan(bm, bv);
2243                         break;
2244                 case M_QUAD_STRIP:
2245                         bevel_build_quadstrip(bm, bv);
2246                         break;
2247         }
2248 }
2249
2250 /* Return the angle between the two faces adjacent to e.
2251  * If there are not two, return 0. */
2252 static float edge_face_angle(EdgeHalf *e)
2253 {
2254         if (e->fprev && e->fnext) {
2255                 /* angle between faces is supplement of angle between face normals */
2256                 return (float)M_PI - angle_normalized_v3v3(e->fprev->no, e->fnext->no);
2257         }
2258         else {
2259                 return 0.0f;
2260         }
2261 }
2262
2263 /* take care, this flag isn't cleared before use, it just so happens that its not set */
2264 #define BM_BEVEL_EDGE_TAG_ENABLE(bme)  BM_ELEM_API_FLAG_ENABLE(  (bme), _FLAG_OVERLAP)
2265 #define BM_BEVEL_EDGE_TAG_DISABLE(bme) BM_ELEM_API_FLAG_DISABLE( (bme), _FLAG_OVERLAP)
2266 #define BM_BEVEL_EDGE_TAG_TEST(bme)    BM_ELEM_API_FLAG_TEST(    (bme), _FLAG_OVERLAP)
2267
2268 /*
2269  * Construction around the vertex
2270  */
2271 static BevVert * bevel_vert_construct(BMesh *bm, BevelParams *bp, BMVert *v)
2272 {
2273         BMEdge *bme;
2274         BevVert *bv;
2275         BMEdge *bme2, *unflagged_bme, *first_bme;
2276         BMFace *f;
2277         BMVert *v1, *v2;
2278         BMIter iter, iter2;
2279         EdgeHalf *e;
2280         float weight, z;
2281         int i, found_shared_face, ccw_test_sum;
2282         int nsel = 0;
2283         int ntot = 0;
2284         int fcnt;
2285
2286         /* Gather input selected edges.
2287          * Only bevel selected edges that have exactly two incident faces.
2288          * Want edges to be ordered so that they share faces.
2289          * There may be one or more chains of shared faces broken by
2290          * gaps where there are no faces.
2291          * TODO: make following work when more than one gap.
2292          */
2293
2294         first_bme = NULL;
2295         BM_ITER_ELEM (bme, &iter, v, BM_EDGES_OF_VERT) {
2296                 fcnt = BM_edge_face_count(bme);
2297                 if (BM_elem_flag_test(bme, BM_ELEM_TAG) && !bp->vertex_only) {
2298                         BLI_assert(fcnt == 2);
2299                         nsel++;
2300                         if (!first_bme)
2301                                 first_bme = bme;
2302                 }
2303                 if (fcnt == 1) {
2304                         /* good to start face chain from this edge */
2305                         first_bme = bme;
2306                 }
2307                 ntot++;
2308
2309                 BM_BEVEL_EDGE_TAG_DISABLE(bme);
2310         }
2311         if (!first_bme)
2312                 first_bme = v->e;
2313
2314         if ((nsel == 0 && !bp->vertex_only) || (ntot < 2 && bp->vertex_only)) {
2315                 /* signal this vert isn't being beveled */
2316                 BM_elem_flag_disable(v, BM_ELEM_TAG);
2317                 return NULL;
2318         }
2319
2320         /* avoid calling BM_vert_edge_count since we loop over edges already */
2321         // ntot = BM_vert_edge_count(v);
2322         // BLI_assert(ntot == BM_vert_edge_count(v));
2323
2324         bv = (BevVert *)BLI_memarena_alloc(bp->mem_arena, (sizeof(BevVert)));
2325         bv->v = v;
2326         bv->edgecount = ntot;
2327         bv->selcount = nsel;
2328         bv->offset = bp->offset;
2329         bv->edges = (EdgeHalf *)BLI_memarena_alloc(bp->mem_arena, ntot * sizeof(EdgeHalf));
2330         bv->vmesh = (VMesh *)BLI_memarena_alloc(bp->mem_arena, sizeof(VMesh));
2331         bv->vmesh->seg = bp->seg;
2332
2333         if (bp->vertex_only) {
2334                 /* if weighted, modify offset by weight */
2335                 if (bp->dvert != NULL && bp->vertex_group != -1) {
2336                         weight = defvert_find_weight(bp->dvert + BM_elem_index_get(v), bp->vertex_group);
2337                         if (weight <= 0.0f) {
2338                                 BM_elem_flag_disable(v, BM_ELEM_TAG);
2339                                 return NULL;
2340                         }
2341                         bv->offset *= weight;
2342                 }
2343         }
2344         BLI_ghash_insert(bp->vert_hash, v, bv);
2345
2346         /* add edges to bv->edges in order that keeps adjacent edges sharing
2347          * a face, if possible */
2348         i = 0;
2349
2350         bme = first_bme;
2351         BM_BEVEL_EDGE_TAG_ENABLE(bme);
2352         e = &bv->edges[0];
2353         e->e = bme;
2354         for (i = 0; i < ntot; i++) {
2355                 if (i > 0) {
2356                         /* find an unflagged edge bme2 that shares a face f with previous bme */
2357                         found_shared_face = 0;
2358                         unflagged_bme = NULL;
2359                         BM_ITER_ELEM (bme2, &iter, v, BM_EDGES_OF_VERT) {
2360                                 if (BM_BEVEL_EDGE_TAG_TEST(bme2))
2361                                         continue;
2362                                 if (!unflagged_bme)
2363                                         unflagged_bme = bme2;
2364                                 if (!bme->l)
2365                                         continue;
2366                                 BM_ITER_ELEM (f, &iter2, bme2, BM_FACES_OF_EDGE) {
2367                                         if (BM_face_edge_share_loop(f, bme)) {
2368                                                 found_shared_face = 1;
2369                                                 break;
2370                                         }
2371                                 }
2372                                 if (found_shared_face)
2373                                         break;
2374                         }
2375                         e = &bv->edges[i];
2376                         if (found_shared_face) {
2377                                 e->e = bme2;
2378                                 e->fprev = f;
2379                                 bv->edges[i - 1].fnext = f;
2380                         }
2381                         else {
2382                                 e->e = unflagged_bme;
2383                         }
2384                 }
2385                 bme = e->e;
2386                 BM_BEVEL_EDGE_TAG_ENABLE(bme);
2387                 if (BM_elem_flag_test(bme, BM_ELEM_TAG) && !bp->vertex_only) {
2388                         e->is_bev = TRUE;
2389                         e->seg = bp->seg;
2390                 }
2391                 else {
2392                         e->is_bev = FALSE;
2393                         e->seg = 0;
2394                 }
2395                 e->is_rev = (bme->v2 == v);
2396         }
2397         /* find wrap-around shared face */
2398         BM_ITER_ELEM (f, &iter2, bme, BM_FACES_OF_EDGE) {
2399                 if (bv->edges[0].e->l && BM_face_edge_share_loop(f, bv->edges[0].e)) {
2400                         if (bv->edges[0].fnext == f)
2401                                 continue;   /* if two shared faces, want the other one now */
2402                         bv->edges[ntot - 1].fnext = f;
2403                         bv->edges[0].fprev = f;
2404                         break;
2405                 }
2406         }
2407
2408         /* if edge array doesn't go CCW around vertex from average normal side,
2409          * reverse the array, being careful to reverse face pointers too */
2410         if (ntot > 1) {
2411                 ccw_test_sum = 0;
2412                 for (i = 0; i < ntot; i++)
2413                         ccw_test_sum += bev_ccw_test(bv->edges[i].e, bv->edges[(i + 1) % ntot].e,
2414                                                      bv->edges[i].fnext);
2415                 if (ccw_test_sum < 0) {
2416                         for (i = 0; i <= (ntot / 2) - 1; i++) {
2417                                 SWAP(EdgeHalf, bv->edges[i], bv->edges[ntot - i - 1]);
2418                                 SWAP(BMFace *, bv->edges[i].fprev, bv->edges[i].fnext);
2419                                 SWAP(BMFace *, bv->edges[ntot - i - 1].fprev, bv->edges[ntot - i - 1].fnext);
2420                         }
2421                         if (ntot % 2 == 1) {
2422                                 i = ntot / 2;
2423                                 SWAP(BMFace *, bv->edges[i].fprev,  bv->edges[i].fnext);
2424                         }
2425                 }
2426         }
2427
2428         for (i = 0, e = bv->edges; i < ntot; i++, e++) {
2429                 e->next = &bv->edges[(i + 1) % ntot];
2430                 e->prev = &bv->edges[(i + ntot - 1) % ntot];
2431
2432                 /* set offsets  */
2433                 if (e->is_bev) {
2434                         /* Convert distance as specified by user into offsets along
2435                          * faces on left side and right side of this edgehalf.
2436                          * Except for percent method, offset will be same on each side. */
2437
2438                         switch (bp->offset_type) {
2439                                 case BEVEL_AMT_OFFSET:
2440                                         e->offset_l_spec = bp->offset;
2441                                         break;
2442                                 case BEVEL_AMT_WIDTH:
2443                                         z = fabsf(2.0f * sinf(edge_face_angle(e) / 2.0f));
2444                                         if (z < BEVEL_EPSILON)
2445                                                 e->offset_l_spec = 0.01f * bp->offset; /* undefined behavior, so tiny bevel */
2446                                         else
2447                                                 e->offset_l_spec = bp->offset / z;
2448                                         break;
2449                                 case BEVEL_AMT_DEPTH:
2450                                         z = fabsf(cosf(edge_face_angle(e) / 2.0f));
2451                                         if (z < BEVEL_EPSILON)
2452                                                 e->offset_l_spec = 0.01f * bp->offset; /* undefined behavior, so tiny bevel */
2453                                         else
2454                                                 e->offset_l_spec = bp->offset / z;
2455                                         break;
2456                                 case BEVEL_AMT_PERCENT:
2457                                         /* offset needs to be such that it meets adjacent edges at percentage of their lengths */
2458                                         v1 = BM_edge_other_vert(e->prev->e, v);
2459                                         v2 = BM_edge_other_vert(e->e, v);
2460                                         z = sinf(angle_v3v3v3(v1->co, v->co, v2->co));
2461                                         e->offset_l_spec = BM_edge_calc_length(e->prev->e) * bp->offset * z / 100.0f;
2462                                         v1 = BM_edge_other_vert(e->e, v);
2463                                         v2 = BM_edge_other_vert(e->next->e, v);
2464                                         z = sinf(angle_v3v3v3(v1->co, v->co, v2->co));
2465                                         e->offset_r_spec = BM_edge_calc_length(e->next->e) * bp->offset * z / 100.0f;
2466                                         break;
2467                                 default:
2468                                         BLI_assert(!"bad bevel offset kind");
2469                                         e->offset_l_spec = bp->offset;
2470                                         break;
2471                         }
2472                         if (bp->offset_type != BEVEL_AMT_PERCENT)
2473                                 e->offset_r_spec = e->offset_l_spec;
2474                         if (bp->use_weights) {
2475                                 weight = BM_elem_float_data_get(&bm->edata, e->e, CD_BWEIGHT);
2476                                 e->offset_l_spec *= weight;
2477                                 e->offset_r_spec *= weight;
2478                         }
2479                 }
2480                 else {
2481                         e->offset_l_spec = e->offset_r_spec = 0.0f;
2482                 }
2483                 e->offset_l = e->offset_l_spec;
2484                 e->offset_r = e->offset_r_spec;
2485
2486                 BM_BEVEL_EDGE_TAG_DISABLE(e->e);
2487                 if (e->fprev && e->fnext)
2488                         e->is_seam = !contig_ldata_across_edge(bm, e->e, e->fprev, e->fnext);
2489                 else
2490                         e->is_seam = true;
2491         }
2492
2493         return bv;
2494 }
2495
2496 /* Face f has at least one beveled vertex.  Rebuild f */
2497 static int bev_rebuild_polygon(BMesh *bm, BevelParams *bp, BMFace *f)
2498 {
2499         BMIter liter;
2500         BMLoop *l, *lprev;
2501         BevVert *bv;
2502         BoundVert *v, *vstart, *vend;
2503         EdgeHalf *e, *eprev;
2504         VMesh *vm;
2505         int i, k;
2506         int do_rebuild = FALSE;
2507         BMVert *bmv;
2508         BMVert **vv = NULL;
2509         BMVert **vv_fix = NULL;
2510         BLI_array_staticdeclare(vv, BM_DEFAULT_NGON_STACK_SIZE);
2511         BLI_array_staticdeclare(vv_fix, BM_DEFAULT_NGON_STACK_SIZE);
2512
2513         BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
2514                 if (BM_elem_flag_test(l->v, BM_ELEM_TAG)) {
2515                         lprev = l->prev;
2516                         bv = find_bevvert(bp, l->v);
2517                         e = find_edge_half(bv, l->e);
2518                         eprev = find_edge_half(bv, lprev->e);
2519                         BLI_assert(e != NULL && eprev != NULL);
2520                         vstart = eprev->leftv;
2521                         if (e->is_bev)
2522                                 vend = e->rightv;
2523                         else
2524                                 vend = e->leftv;
2525                         v = vstart;
2526                         vm = bv->vmesh;
2527                         BLI_array_append(vv, v->nv.v);
2528                         while (v != vend) {
2529                                 if (vm->mesh_kind == M_NONE && v->ebev && v->ebev->seg > 1 && v->ebev != e && v->ebev != eprev) {
2530                                         /* case of 3rd face opposite a beveled edge, with no vmesh */
2531                                         i = v->index;
2532                                         e = v->ebev;
2533                                         for (k = 1; k < e->seg; k++) {
2534                                                 bmv = mesh_vert(vm, i, 0, k)->v;
2535                                                 BLI_array_append(vv, bmv);
2536                                                 /* may want to merge UVs of these later */
2537                                                 if (!e->is_seam)
2538                                                         BLI_array_append(vv_fix, bmv);
2539                                         }
2540                                 }
2541                                 else if (bp->vertex_only && vm->mesh_kind == M_ADJ_SUBDIV && vm->seg > 1) {
2542                                         BLI_assert(v->prev == vend);
2543                                         i = vend->index;
2544                                         for (k = vm->seg - 1; k > 0; k--) {
2545                                                 bmv = mesh_vert(vm, i, 0, k)->v;
2546                                                 BLI_array_append(vv, bmv);
2547                                         }
2548                                 }
2549                                 v = v->prev;
2550                                 BLI_array_append(vv, v->nv.v);
2551                         }
2552
2553                         do_rebuild = TRUE;
2554                 }
2555                 else {
2556                         BLI_array_append(vv, l->v);
2557                 }
2558         }
2559         if (do_rebuild) {
2560                 BMFace *f_new = bev_create_ngon(bm, vv, BLI_array_count(vv), NULL, f, true);
2561
2562                 for (k = 0; k < BLI_array_count(vv_fix); k++) {
2563                         bev_merge_uvs(bm, vv_fix[k]);
2564                 }
2565
2566                 /* don't select newly created boundary faces... */
2567                 if (f_new) {
2568                         BM_elem_flag_disable(f_new, BM_ELEM_TAG);
2569                 }
2570         }
2571
2572         BLI_array_free(vv);
2573         return do_rebuild;
2574 }
2575
2576 /* All polygons touching v need rebuilding because beveling v has made new vertices */
2577 static void bevel_rebuild_existing_polygons(BMesh *bm, BevelParams *bp, BMVert *v)
2578 {
2579         void    *faces_stack[BM_DEFAULT_ITER_STACK_SIZE];
2580         int      faces_len, f_index;
2581         BMFace **faces = BM_iter_as_arrayN(bm, BM_FACES_OF_VERT, v, &faces_len,
2582                                            faces_stack, BM_DEFAULT_ITER_STACK_SIZE);
2583
2584         if (LIKELY(faces != NULL)) {
2585                 for (f_index = 0; f_index < faces_len; f_index++) {
2586                         BMFace *f = faces[f_index];
2587                         if (bev_rebuild_polygon(bm, bp, f)) {
2588                                 BM_face_kill(bm, f);
2589                         }
2590                 }
2591
2592                 if (faces != (BMFace **)faces_stack) {
2593                         MEM_freeN(faces);
2594                 }
2595         }
2596 }
2597
2598 static void bev_merge_end_uvs(BMesh *bm, BevVert *bv, EdgeHalf *e)
2599 {
2600         VMesh *vm = bv->vmesh;
2601         int i, k, nseg;
2602
2603         nseg = e->seg;
2604         i = e->leftv->index;
2605         for (k = 1; k < nseg; k++) {
2606                 bev_merge_uvs(bm, mesh_vert(vm, i, 0, k)->v);
2607         }
2608 }
2609
2610 /*
2611  * Build the polygons along the selected Edge
2612  */
2613 static void bevel_build_edge_polygons(BMesh *bm, BevelParams *bp, BMEdge *bme)
2614 {
2615         BevVert *bv1, *bv2;
2616         BMVert *bmv1, *bmv2, *bmv3, *bmv4, *bmv1i, *bmv2i, *bmv3i, *bmv4i;
2617         VMesh *vm1, *vm2;
2618         EdgeHalf *e1, *e2;
2619         BMEdge *bme1, *bme2;
2620         BMFace *f1, *f2, *f;
2621         int k, nseg, i1, i2, odd, mid;
2622
2623         if (!BM_edge_is_manifold(bme))
2624                 return;
2625
2626         bv1 = find_bevvert(bp, bme->v1);
2627         bv2 = find_bevvert(bp, bme->v2);
2628
2629         BLI_assert(bv1 && bv2);
2630
2631         e1 = find_edge_half(bv1, bme);
2632         e2 = find_edge_half(bv2, bme);
2633
2634         BLI_assert(e1 && e2);
2635
2636         /*   v4             v3
2637          *    \            /
2638          *     e->v1 - e->v2
2639          *    /            \
2640          *   v1             v2
2641          */
2642         nseg = e1->seg;
2643         BLI_assert(nseg > 0 && nseg == e2->seg);
2644
2645         bmv1 = e1->leftv->nv.v;
2646         bmv4 = e1->rightv->nv.v;
2647         bmv2 = e2->rightv->nv.v;
2648         bmv3 = e2->leftv->nv.v;
2649
2650         BLI_assert(bmv1 && bmv2 && bmv3 && bmv4);
2651
2652         f1 = e1->fprev;
2653         f2 = e1->fnext;
2654
2655         if (nseg == 1) {
2656                 bev_create_quad_straddle(bm, bmv1, bmv2, bmv3, bmv4, f1, f2, e1->is_seam);
2657         }
2658         else {
2659                 i1 = e1->leftv->index;
2660                 i2 = e2->leftv->index;
2661                 vm1 = bv1->vmesh;
2662                 vm2 = bv2->vmesh;
2663                 bmv1i = bmv1;
2664                 bmv2i = bmv2;
2665                 odd = nseg % 2;
2666                 mid = nseg / 2;
2667                 for (k = 1; k <= nseg; k++) {
2668                         bmv4i = mesh_vert(vm1, i1, 0, k)->v;
2669                         bmv3i = mesh_vert(vm2, i2, 0, nseg - k)->v;
2670                         if (odd && k == mid + 1) {
2671                                 bev_create_quad_straddle(bm, bmv1i, bmv2i, bmv3i, bmv4i, f1, f2, e1->is_seam);
2672                         }
2673                         else {
2674                                 f = (k <= mid) ? f1 : f2;
2675                                 bev_create_quad_tri(bm, bmv1i, bmv2i, bmv3i, bmv4i, f, true);
2676                         }
2677                         bmv1i = bmv4i;
2678                         bmv2i = bmv3i;
2679                 }
2680                 if (!odd && !e1->is_seam) {
2681                         bev_merge_uvs(bm, mesh_vert(vm1, i1, 0, mid)->v);
2682                         bev_merge_uvs(bm, mesh_vert(vm2, i2, 0, mid)->v);
2683                 }
2684         }
2685
2686         /* Fix UVs along end edge joints.  A nop unless other side built already. */
2687         if (!e1->is_seam && bv1->vmesh->mesh_kind == M_NONE)
2688                 bev_merge_end_uvs(bm, bv1, e1);
2689         if (!e2->is_seam && bv2->vmesh->mesh_kind == M_NONE)
2690                 bev_merge_end_uvs(bm, bv2, e2);
2691
2692         /* Copy edge data to first and last edge */
2693         bme1 = BM_edge_exists(bmv1, bmv2);
2694         bme2 = BM_edge_exists(bmv3, bmv4);
2695         BLI_assert(bme1 && bme2);
2696         BM_elem_attrs_copy(bm, bm, bme, bme1);
2697         BM_elem_attrs_copy(bm, bm, bme, bme2);
2698 }
2699
2700 /*
2701  * Calculate and return an offset that is the lesser of the current
2702  * bp.offset and the maximum possible offset before geometry
2703  * collisions happen.
2704  * Currently this is a quick and dirty estimate of the max
2705  * possible: half the minimum edge length of any vertex involved
2706  * in a bevel. This is usually conservative.
2707  * The correct calculation is quite complicated.
2708  * TODO: implement this correctly.
2709  */
2710 static float bevel_limit_offset(BMesh *bm, BevelParams *bp)
2711 {
2712         BMVert *v;
2713         BMEdge *e;
2714         BMIter v_iter, e_iter;
2715         float limited_offset, half_elen;
2716         bool vbeveled;
2717
2718         limited_offset = bp->offset;
2719         BM_ITER_MESH (v, &v_iter, bm, BM_VERTS_OF_MESH) {
2720                 if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
2721                         if (bp->vertex_only) {
2722                                 vbeveled = true;
2723                         }
2724                         else {
2725                                 vbeveled = false;
2726                                 BM_ITER_ELEM (e, &e_iter, v, BM_EDGES_OF_VERT) {
2727                                         if (BM_elem_flag_test(BM_edge_other_vert(e, v), BM_ELEM_TAG)) {
2728                                                 vbeveled = true;
2729                                                 break;
2730                                         }
2731                                 }
2732                         }
2733                         if (vbeveled) {
2734                                 BM_ITER_ELEM (e, &e_iter, v, BM_EDGES_OF_VERT) {
2735                                         half_elen = 0.5f * BM_edge_calc_length(e);
2736                                         if (half_elen < limited_offset)
2737                                                 limited_offset = half_elen;
2738                                 }
2739                         }
2740                 }
2741         }
2742         return limited_offset;
2743 }
2744
2745 /**
2746  * - Currently only bevels BM_ELEM_TAG'd verts and edges.
2747  *
2748  * - Newly created faces are BM_ELEM_TAG'd too,
2749  *   the caller needs to ensure this is cleared before calling
2750  *   if its going to use this face tag.
2751  *
2752  * - If limit_offset is set, adjusts offset down if necessary
2753  *   to avoid geometry collisions.
2754  *
2755  * \warning all tagged edges _must_ be manifold.
2756  */
2757 void BM_mesh_bevel(BMesh *bm, const float offset, const int offset_type, const float segments,
2758                    const bool vertex_only, const bool use_weights, const bool limit_offset,
2759                    const struct MDeformVert *dvert, const int vertex_group)
2760 {
2761         BMIter iter;
2762         BMVert *v, *v_next;
2763         BMEdge *e;
2764         BevVert *bv;
2765         BevelParams bp = {NULL};
2766
2767         bp.offset = offset;
2768         bp.offset_type = offset_type;
2769         bp.seg    = segments;
2770         bp.vertex_only = vertex_only;
2771         bp.use_weights = use_weights;
2772         bp.preserve_widths = false;
2773         bp.limit_offset = limit_offset;
2774         bp.dvert = dvert;
2775         bp.vertex_group = vertex_group;
2776
2777         if (bp.offset > 0) {
2778                 /* primary alloc */
2779                 bp.vert_hash = BLI_ghash_ptr_new(__func__);
2780                 bp.mem_arena = BLI_memarena_new(MEM_SIZE_OPTIMAL(1 << 16), __func__);
2781                 BLI_memarena_use_calloc(bp.mem_arena);
2782
2783                 if (limit_offset)
2784                         bp.offset = bevel_limit_offset(bm, &bp);
2785
2786                 /* Analyze input vertices, sorting edges and assigning initial new vertex positions */
2787                 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
2788                         if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
2789                                 bv = bevel_vert_construct(bm, &bp, v);
2790                                 if (bv)
2791                                         build_boundary(&bp, bv, true);
2792                         }
2793                 }
2794
2795                 /* Perhaps do a pass to try to even out widths */
2796                 if (!bp.vertex_only) {
2797                         adjust_offsets(&bp);
2798                 }
2799
2800                 /* Build the meshes around vertices, now that positions are final */
2801                 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
2802                         if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
2803                                 bv = find_bevvert(&bp, v);
2804                                 if (bv)
2805                                         build_vmesh(&bp, bm, bv);
2806                         }
2807                 }
2808
2809                 /* Build polygons for edges */
2810                 if (!bp.vertex_only) {
2811                         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
2812                                 if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
2813                                         bevel_build_edge_polygons(bm, &bp, e);
2814                                 }
2815                         }
2816                 }
2817
2818                 /* Rebuild face polygons around affected vertices */
2819                 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
2820                         if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
2821                                 bevel_rebuild_existing_polygons(bm, &bp, v);
2822                         }
2823                 }
2824
2825                 BM_ITER_MESH_MUTABLE (v, v_next, &iter, bm, BM_VERTS_OF_MESH) {
2826                         if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
2827                                 BLI_assert(find_bevvert(&bp, v) != NULL);
2828                                 BM_vert_kill(bm, v);
2829                         }
2830                 }
2831
2832                 /* primary free */
2833                 BLI_ghash_free(bp.vert_hash, NULL, NULL);
2834                 BLI_memarena_free(bp.mem_arena);
2835         }
2836 }