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