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