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