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