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