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