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