source/blender/bmesh/tools/bmesh_bevel.c

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