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