improvements to bevel
[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
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);
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_staticdeclare(ee, BM_DEFAULT_NGON_STACK_SIZE);
268
269                 BLI_array_grow_items(ee, totv);
270                 for (i = 0; i < totv; i++) {
271                         ee[i] = BM_edge_create(bm, vert_arr[i], vert_arr[(i + 1) % totv], NULL, TRUE);
272                 }
273                 f = BM_face_create_ngon(bm, vert_arr[0], vert_arr[1], ee, totv, FALSE);
274                 BLI_array_free(ee);
275         }
276         if (facerep && f) {
277                 int has_mdisps = CustomData_has_layer(&bm->ldata, CD_MDISPS);
278                 BM_elem_attrs_copy(bm, bm, facerep, f);
279                 BM_ITER_ELEM (l, &iter, f, BM_LOOPS_OF_FACE) {
280                         BM_loop_interp_from_face(bm, l, facerep, TRUE, TRUE);
281                         if (has_mdisps)
282                                 BM_loop_interp_multires(bm, l, facerep);
283                 }
284         }
285
286         /* not essential for bevels own internal logic,
287          * this is done so the operator can select newly created faces */
288         if (f) {
289                 BM_elem_flag_enable(f, BM_ELEM_TAG);
290         }
291
292         return f;
293 }
294
295 static BMFace *bev_create_quad_tri(BMesh *bm, BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4,
296                                    BMFace *facerep)
297 {
298         BMVert *varr[4];
299
300         varr[0] = v1;
301         varr[1] = v2;
302         varr[2] = v3;
303         varr[3] = v4;
304         return bev_create_ngon(bm, varr, v4 ? 4 : 3, facerep);
305 }
306
307 /*
308  * Calculate the meeting point between the offset edges for e1 and e2, putting answer in meetco.
309  * e1 and e2 share vertex v and face f (may be NULL) and viewed from the normal side of
310  * the bevel vertex,  e1 precedes e2 in CCW order.
311  * If on_right is true, offset edge is on right of both edges, where e1 enters v and
312  * e2 leave it. If on_right is false, then the offset edge is on the left.
313  * When offsets are equal, the new point is on the edge bisector, with length offset/sin(angle/2),
314  * but if the offsets are not equal (allowing for this, as bevel modifier has edge weights that may
315  * lead to different offsets) then meeting point can be found be intersecting offset lines.
316  */
317 static void offset_meet(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, BMFace *f,
318                         int on_right, float meetco[3])
319 {
320         float dir1[3], dir2[3], norm_v[3], norm_perp1[3], norm_perp2[3],
321               off1a[3], off1b[3], off2a[3], off2b[3], isect2[3];
322
323         /* get direction vectors for two offset lines */
324         sub_v3_v3v3(dir1, v->co, BM_edge_other_vert(e1->e, v)->co);
325         sub_v3_v3v3(dir2, BM_edge_other_vert(e2->e, v)->co, v->co);
326
327         /* get normal to plane where meet point should be */
328         cross_v3_v3v3(norm_v, dir2, dir1);
329         normalize_v3(norm_v);
330         if (!on_right)
331                 negate_v3(norm_v);
332         if (is_zero_v3(norm_v)) {
333                 /* special case: e1 and e2 are parallel; put offset point perp to both, from v.
334                  * need to find a suitable plane.
335                  * if offsets are different, we're out of luck: just use e1->offset */
336                 if (f)
337                         copy_v3_v3(norm_v, f->no);
338                 else
339                         copy_v3_v3(norm_v, v->no);
340                 cross_v3_v3v3(norm_perp1, dir1, norm_v);
341                 normalize_v3(norm_perp1);
342                 copy_v3_v3(off1a, v->co);
343                 madd_v3_v3fl(off1a, norm_perp1, e1->offset);
344                 copy_v3_v3(meetco, off1a);
345         }
346         else {
347                 /* get vectors perp to each edge, perp to norm_v, and pointing into face */
348                 if (f) {
349                         copy_v3_v3(norm_v, f->no);
350                 }
351                 cross_v3_v3v3(norm_perp1, dir1, norm_v);
352                 cross_v3_v3v3(norm_perp2, dir2, norm_v);
353                 normalize_v3(norm_perp1);
354                 normalize_v3(norm_perp2);
355
356                 /* get points that are offset distances from each line, then another point on each line */
357                 copy_v3_v3(off1a, v->co);
358                 madd_v3_v3fl(off1a, norm_perp1, e1->offset);
359                 add_v3_v3v3(off1b, off1a, dir1);
360                 copy_v3_v3(off2a, v->co);
361                 madd_v3_v3fl(off2a, norm_perp2, e2->offset);
362                 add_v3_v3v3(off2b, off2a, dir2);
363
364                 /* intersect the lines; by construction they should be on the same plane and not parallel */
365                 if (!isect_line_line_v3(off1a, off1b, off2a, off2b, meetco, isect2)) {
366                         BLI_assert(!"offset_meet failure");
367                         copy_v3_v3(meetco, off1a);  /* just to do something */
368                 }
369         }
370 }
371
372 /* Like offset_meet, but here f1 and f2 must not be NULL and give the
373  * planes in which to run the offset lines.  They may not meet exactly,
374  * but the line intersection routine will find the closest approach point. */
375 static void offset_in_two_planes(EdgeHalf *e1, EdgeHalf *e2, BMVert *v,
376                                  BMFace *f1, BMFace *f2, float meetco[3])
377 {
378         float dir1[3], dir2[3], norm_perp1[3], norm_perp2[3],
379               off1a[3], off1b[3], off2a[3], off2b[3], isect2[3];
380
381         BLI_assert(f1 != NULL && f2 != NULL);
382
383         /* get direction vectors for two offset lines */
384         sub_v3_v3v3(dir1, v->co, BM_edge_other_vert(e1->e, v)->co);
385         sub_v3_v3v3(dir2, BM_edge_other_vert(e2->e, v)->co, v->co);
386
387         /* get directions into offset planes */
388         cross_v3_v3v3(norm_perp1, dir1, f1->no);
389         normalize_v3(norm_perp1);
390         cross_v3_v3v3(norm_perp2, dir2, f2->no);
391         normalize_v3(norm_perp2);
392
393         /* get points that are offset distances from each line, then another point on each line */
394         copy_v3_v3(off1a, v->co);
395         madd_v3_v3fl(off1a, norm_perp1, e1->offset);
396         add_v3_v3v3(off1b, off1a, dir1);
397         copy_v3_v3(off2a, v->co);
398         madd_v3_v3fl(off2a, norm_perp2, e2->offset);
399         add_v3_v3v3(off2b, off2a, dir2);
400
401         if (angle_v3v3(dir1, dir2) < (float)BEVEL_EPSILON) {
402                 /* lines are parallel; off1a is a good meet point */
403                 copy_v3_v3(meetco, off1a);
404         }
405         else if (!isect_line_line_v3(off1a, off1b, off2a, off2b, meetco, isect2)) {
406                 /* another test says they are parallel */
407                 copy_v3_v3(meetco, off1a);
408         }
409 }
410
411 /* Offset by e->offset in plane with normal plane_no, on left if left==TRUE,
412  * else on right.  If no is NULL, choose an arbitrary plane different
413  * from eh's direction. */
414 static void offset_in_plane(EdgeHalf *e, const float plane_no[3], int left, float r[3])
415 {
416         float dir[3], no[3];
417         BMVert *v;
418
419         v = e->is_rev ? e->e->v1 : e->e->v2;
420
421         sub_v3_v3v3(dir, BM_edge_other_vert(e->e, v)->co, v->co);
422         normalize_v3(dir);
423         if (plane_no) {
424                 copy_v3_v3(no, plane_no);
425         }
426         else {
427                 zero_v3(no);
428                 if (fabs(dir[0]) < fabs(dir[1]))
429                         no[0] = 1.0f;
430                 else
431                         no[1] = 1.0f;
432         }
433         if (left)
434                 cross_v3_v3v3(r, no, dir);
435         else
436                 cross_v3_v3v3(r, dir, no);
437         normalize_v3(r);
438         mul_v3_fl(r, e->offset);
439 }
440
441 /* Calculate coordinates of a point a distance d from v on e->e and return it in slideco */
442 static void slide_dist(EdgeHalf *e, BMVert *v, float d, float slideco[3])
443 {
444         float dir[3], len;
445
446         sub_v3_v3v3(dir, v->co, BM_edge_other_vert(e->e, v)->co);
447         len = normalize_v3(dir);
448         if (d > len)
449                 d = len - (float)(50.0 * BEVEL_EPSILON);
450         copy_v3_v3(slideco, v->co);
451         madd_v3_v3fl(slideco, dir, -d);
452 }
453
454 /* Calculate the point on e where line (co_a, co_b) comes closest to and return it in projco */
455 static void project_to_edge(BMEdge *e, const float co_a[3], const float co_b[3], float projco[3])
456 {
457         float otherco[3];
458
459         if (!isect_line_line_v3(e->v1->co, e->v2->co, co_a, co_b, projco, otherco)) {
460                 BLI_assert(!"project meet failure");
461                 copy_v3_v3(projco, e->v1->co);
462         }
463 }
464
465 /* return 1 if a and b are in CCW order on the normal side of f,
466  * and -1 if they are reversed, and 0 if there is no shared face f */
467 static int bev_ccw_test(BMEdge *a, BMEdge *b, BMFace *f)
468 {
469         BMLoop *la, *lb;
470
471         if (!f)
472                 return 0;
473         la = BM_face_edge_share_loop(f, a);
474         lb = BM_face_edge_share_loop(f, b);
475         if (!la || !lb)
476                 return 0;
477         return lb->next == la ? 1 : -1;
478 }
479
480 #ifdef USE_ALTERNATE_ADJ
481
482 static void vmesh_cent(VMesh *vm, float r_cent[3])
483 {
484         BoundVert *v;
485         int tot = 0;
486         zero_v3(r_cent);
487
488         v = vm->boundstart;
489         do {
490                 add_v3_v3(r_cent, v->nv.co);
491                 tot++;
492         } while ((v = v->next) != vm->boundstart);
493         mul_v3_fl(r_cent, 1.0f / (float)tot);
494 }
495
496 /**
497  *
498  * This example shows a tri fan of quads,
499  * but could be an NGon fan of quads too.
500  * <pre>
501  *      The whole triangle   X
502  *      represents the      / \
503  *      new bevel face.    /   \
504  *                        /     \
505  *       Split into      /       \
506  *       a quad fan.    /         \
507  *                     /           \
508  *                    /             \
509  *                   /               \
510  *          co_prev +-.             .-+
511  *                 /   `-._     _.-'   \
512  *                / co_cent`-+-'        \
513  *               /           |           \
514  * Quad of      /            |            \
515  * interest -- / ---> X      |             \
516  *            /              |              \
517  *           /               |               \
518  *          /         co_next|                \
519  * co_orig +-----------------+-----------------+
520  *
521  *         For each quad, calcualte UV's based on the following:
522  *           U = k    / (vm->seg * 2)
523  *           V = ring / (vm->seg * 2)
524  *           quad = (co_orig, co_prev, co_cent, co_next)
525  *           ... note that co_cent is the same for all quads in the fan.
526  * </pre>
527  *
528  */
529
530 static void get_point_uv(float uv[2],
531                          /* all these args are int's originally
532                           * but pass as floats to the function */
533                          const float seg, const float ring, const float k)
534 {
535         uv[0] = (ring / seg) * 2.0f;
536         uv[1] = (k    / seg) * 2.0f;
537 }
538
539 /* TODO: make this a lot smarter!,
540  * this is the main reason USE_ALTERNATE_ADJ isn't so good right now :S */
541 static float get_point_uv_factor(const float uv[2])
542 {
543         return sinf(1.0f - max_ff(uv[0], uv[1]) / 2.0f);
544 }
545
546 static void get_point_on_round_edge(const float uv[2],
547                                     float quad[4][3],
548                                     float r_co[3])
549 {
550         interp_bilinear_quad_v3(quad, uv[0], uv[1], r_co);
551 }
552
553 #else  /* USE_ALTERNATE_ADJ */
554
555 /*
556  * calculation of points on the round profile
557  * r - result, coordinate of point on round profile
558  * method:
559  * Inscribe a circle in angle va - v -vb
560  * such that it touches the arms at offset from v.
561  * Rotate the center-va segment by (i/n) of the
562  * angle va - center -vb, and put the endpoint
563  * of that segment in r.
564  */
565 static void get_point_on_round_profile(float r_co[3], float offset, int k, int count,
566                                        const float va[3], const float v[3], const float vb[3])
567 {
568         float vva[3], vvb[3], angle, center[3], rv[3], axis[3], co[3];
569
570         sub_v3_v3v3(vva, va, v);
571         sub_v3_v3v3(vvb, vb, v);
572         normalize_v3(vva);
573         normalize_v3(vvb);
574         angle = angle_normalized_v3v3(vva, vvb);
575
576         add_v3_v3v3(center, vva, vvb);
577         normalize_v3(center);
578         mul_v3_fl(center, offset * (1.0f / cosf(0.5f * angle)));
579         add_v3_v3(center, v);           /* coordinates of the center of the inscribed circle */
580
581
582         sub_v3_v3v3(rv, va, center);    /* radius vector */
583
584
585         sub_v3_v3v3(co, v, center);
586         cross_v3_v3v3(axis, rv, co);    /* calculate axis */
587
588         sub_v3_v3v3(vva, va, center);
589         sub_v3_v3v3(vvb, vb, center);
590         angle = angle_v3v3(vva, vvb);
591
592         rotate_v3_v3v3fl(co, rv, axis, angle * (float)k / (float)count);
593
594         add_v3_v3(co, center);
595         copy_v3_v3(r_co, co);
596 }
597
598 /*
599  * Find the point (/n) of the way around the round profile for e,
600  * where start point is va, midarc point is vmid, and end point is vb.
601  * Return the answer in profileco.
602  * Method:
603  * Adjust va and vb (along edge direction) so that they are perpendicular
604  * to edge at v, then use get_point_on_round_profile, then project
605  * back onto original va - vmid - vb plane.
606  * If va, vmid, and vb are all on the same plane, just interpolate between va and vb.
607  */
608 static void get_point_on_round_edge(EdgeHalf *e, int k,
609                                     const float va[3], const float vmid[3], const float vb[3],
610                                     float r_co[3])
611 {
612         float vva[3], vvb[3],  point[3], dir[3], vaadj[3], vbadj[3], p2[3], pn[3];
613         int n = e->seg;
614
615         sub_v3_v3v3(vva, va, vmid);
616         sub_v3_v3v3(vvb, vb, vmid);
617         if (e->is_rev)
618                 sub_v3_v3v3(dir, e->e->v1->co, e->e->v2->co);
619         else
620                 sub_v3_v3v3(dir, e->e->v2->co, e->e->v1->co);
621         normalize_v3(dir);
622         if (fabsf(angle_v3v3(vva, vvb) - (float)M_PI) > (float)BEVEL_EPSILON) {
623                 copy_v3_v3(vaadj, va);
624                 madd_v3_v3fl(vaadj, dir, -len_v3(vva) * cosf(angle_v3v3(vva, dir)));
625                 copy_v3_v3(vbadj, vb);
626                 madd_v3_v3fl(vbadj, dir, -len_v3(vvb) * cosf(angle_v3v3(vvb, dir)));
627
628                 get_point_on_round_profile(point, e->offset, k, n, vaadj, vmid, vbadj);
629
630                 add_v3_v3v3(p2, point, dir);
631                 cross_v3_v3v3(pn, vva, vvb);
632                 if (!isect_line_plane_v3(r_co, point, p2, vmid, pn, 0)) {
633                         /* TODO: track down why this sometimes fails */
634                         copy_v3_v3(r_co, point);
635                 }
636         }
637         else {
638                 /* planar case */
639                 interp_v3_v3v3(r_co, va, vb, (float)k / (float)n);
640         }
641 }
642
643 #endif  /* !USE_ALTERNATE_ADJ */
644
645 /* Make a circular list of BoundVerts for bv, each of which has the coordinates
646  * of a vertex on the the boundary of the beveled vertex bv->v.
647  * Also decide on the mesh pattern that will be used inside the boundary.
648  * Doesn't make the actual BMVerts */
649 static void build_boundary(MemArena *mem_arena, BevVert *bv)
650 {
651         EdgeHalf *efirst, *e;
652         BoundVert *v;
653         VMesh *vm;
654         float co[3];
655         const float  *no;
656         float lastd;
657
658         e = efirst = next_bev(bv, NULL);
659         vm = bv->vmesh;
660
661         BLI_assert(bv->edgecount >= 2);  /* since bevel edges incident to 2 faces */
662
663         if (bv->edgecount == 2 && bv->selcount == 1) {
664                 /* special case: beveled edge meets non-beveled one at valence 2 vert */
665                 no = e->fprev ? e->fprev->no : (e->fnext ? e->fnext->no : NULL);
666                 offset_in_plane(e, no, TRUE, co);
667                 v = add_new_bound_vert(mem_arena, vm, co);
668                 v->efirst = v->elast = v->ebev = e;
669                 e->leftv = v;
670                 no = e->fnext ? e->fnext->no : (e->fprev ? e->fprev->no : NULL);
671                 offset_in_plane(e, no, FALSE, co);
672                 v = add_new_bound_vert(mem_arena, vm, co);
673                 v->efirst = v->elast = e;
674                 e->rightv = v;
675                 /* make artifical extra point along unbeveled edge, and form triangle */
676                 slide_dist(e->next, bv->v, e->offset, co);
677                 v = add_new_bound_vert(mem_arena, vm, co);
678                 v->efirst = v->elast = e->next;
679                 vm->mesh_kind = M_POLY;
680                 return;
681         }
682
683         lastd = e->offset;
684         vm->boundstart = NULL;
685         do {
686                 if (e->is_bev) {
687                         /* handle only left side of beveled edge e here: next iteration should do right side */
688                         if (e->prev->is_bev) {
689                                 BLI_assert(e->prev != e);  /* see: wire edge special case */
690                                 offset_meet(e->prev, e, bv->v, e->fprev, TRUE, co);
691                                 v = add_new_bound_vert(mem_arena, vm, co);
692                                 v->efirst = e->prev;
693                                 v->elast = v->ebev = e;
694                                 e->leftv = v;
695                                 e->prev->rightv = v;
696                         }
697                         else {
698                                 /* e->prev is not beveled */
699                                 if (e->prev->prev->is_bev) {
700                                         BLI_assert(e->prev->prev != e); /* see: edgecount 2, selcount 1 case */
701                                         /* find meet point between e->prev->prev and e and attach e->prev there */
702                                         /* TODO: fix case when one or both faces in following are NULL */
703                                         offset_in_two_planes(e->prev->prev, e, bv->v,
704                                                              e->prev->prev->fnext, e->fprev, co);
705                                         v = add_new_bound_vert(mem_arena, vm, co);
706                                         v->efirst = e->prev->prev;
707                                         v->elast = v->ebev = e;
708                                         e->leftv = v;
709                                         e->prev->leftv = v;
710                                         e->prev->prev->rightv = v;
711                                 }
712                                 else {
713                                         /* neither e->prev nor e->prev->prev are beveled: make on-edge on e->prev */
714                                         offset_meet(e->prev, e, bv->v, e->fprev, TRUE, co);
715                                         v = add_new_bound_vert(mem_arena, vm, co);
716                                         v->efirst = e->prev;
717                                         v->elast = v->ebev = e;
718                                         e->leftv = v;
719                                         e->prev->leftv = v;
720                                 }
721                         }
722                         lastd = len_v3v3(bv->v->co, v->nv.co);
723                 }
724                 else {
725                         /* e is not beveled */
726                         if (e->next->is_bev) {
727                                 /* next iteration will place e between beveled previous and next edges */
728                                 /* do nothing... */
729                         }
730                         else if (e->prev->is_bev) {
731                                 /* on-edge meet between e->prev and e */
732                                 offset_meet(e->prev, e, bv->v, e->fprev, TRUE, co);
733                                 v = add_new_bound_vert(mem_arena, vm, co);
734                                 v->efirst = e->prev;
735                                 v->elast = e;
736                                 e->leftv = v;
737                                 e->prev->rightv = v;
738                         }
739                         else {
740                                 /* None of e->prev, e, e->next are beveled.
741                                  * could either leave alone or add slide points to make
742                                  * one polygon around bv->v.  For now, we choose latter.
743                                  * Could slide to make an even bevel plane but for now will
744                                  * just use last distance a meet point moved from bv->v. */
745                                 slide_dist(e, bv->v, lastd, co);
746                                 v = add_new_bound_vert(mem_arena, vm, co);
747                                 v->efirst = v->elast = e;
748                                 e->leftv = v;
749                         }
750                 }
751         } while ((e = e->next) != efirst);
752
753         BLI_assert(vm->count >= 2);
754         if (vm->count == 2 && bv->edgecount == 3) {
755                 vm->mesh_kind = M_NONE;
756         }
757         else if (bv->selcount == 2) {
758                 vm->mesh_kind = M_QUAD_STRIP;
759         }
760         else if (efirst->seg == 1 || bv->selcount == 1) {
761                 if (vm->count == 3 && bv->selcount == 1) {
762                         vm->mesh_kind = M_TRI_FAN;
763                 }
764                 else {
765                         vm->mesh_kind = M_POLY;
766                 }
767         }
768         else {
769                 vm->mesh_kind = M_ADJ;
770         }
771         /* TODO: if vm->count == 4 and bv->selcount == 4, use M_CROSS pattern */
772 }
773
774 /*
775  * Given that the boundary is built and the boundary BMVerts have been made,
776  * calculate the positions of the interior mesh points for the M_ADJ pattern,
777  * then make the BMVerts and the new faces. */
778 static void bevel_build_rings(BMesh *bm, BevVert *bv)
779 {
780         int k, ring, i, n, ns, ns2, nn;
781         VMesh *vm = bv->vmesh;
782         BoundVert *v, *vprev, *vnext;
783         NewVert *nv, *nvprev, *nvnext;
784         BMVert *bmv, *bmv1, *bmv2, *bmv3, *bmv4;
785         BMFace *f;
786         float co[3], coa[3], cob[3], midco[3];
787
788 #ifdef USE_ALTERNATE_ADJ
789         /* ordered as follows (orig, prev, center, next)*/
790         float quad_plane[4][3];
791         float quad_orig[4][3];
792 #endif
793
794
795 #ifdef USE_ALTERNATE_ADJ
796         /* the rest are initialized inline, this remains the same for all */
797         vmesh_cent(vm, quad_plane[2]);
798         copy_v3_v3(quad_orig[2], bv->v->co);
799 #endif
800
801         n = vm->count;
802         ns = vm->seg;
803         ns2 = ns / 2;
804         BLI_assert(n > 2 && ns > 1);
805         /* Make initial rings, going between points on neighbors.
806          * After this loop, will have coords for all (i, r, k) where
807          * BoundVert for i has a bevel, 0 <= r <= ns2, 0 <= k <= ns */
808         for (ring = 1; ring <= ns2; ring++) {
809                 v = vm->boundstart;
810
811                 do {
812                         i = v->index;
813                         if (v->ebev) {
814                                 /* get points coords of points a and b, on outer rings
815                                  * of prev and next edges, k away from this edge */
816                                 vprev = v->prev;
817                                 vnext = v->next;
818
819                                 if (vprev->ebev)
820                                         nvprev = mesh_vert(vm, vprev->index, 0, ns - ring);
821                                 else
822                                         nvprev = mesh_vert(vm, vprev->index, 0, ns);
823                                 copy_v3_v3(coa, nvprev->co);
824                                 nv = mesh_vert(vm, i, ring, 0);
825                                 copy_v3_v3(nv->co, coa);
826                                 nv->v = nvprev->v;
827
828                                 if (vnext->ebev)
829                                         nvnext = mesh_vert(vm, vnext->index, 0, ring);
830                                 else
831                                         nvnext = mesh_vert(vm, vnext->index, 0, 0);
832                                 copy_v3_v3(cob, nvnext->co);
833                                 nv = mesh_vert(vm, i, ring, ns);
834                                 copy_v3_v3(nv->co, cob);
835                                 nv->v = nvnext->v;
836
837 #ifdef USE_ALTERNATE_ADJ
838                                 /* plane */
839                                 copy_v3_v3(quad_plane[0], v->nv.co);
840                                 mid_v3_v3v3(quad_plane[1], v->nv.co, v->prev->nv.co);
841                                 /* quad[2] is set */
842                                 mid_v3_v3v3(quad_plane[3], v->nv.co, v->next->nv.co);
843
844                                 /* orig */
845                                 copy_v3_v3(quad_orig[0], v->nv.co);  /* only shared location between 2 quads */
846                                 project_to_edge(v->ebev->prev->e, v->nv.co, v->prev->nv.co, quad_orig[1]);
847                                 project_to_edge(v->ebev->e,       v->nv.co, v->next->nv.co, quad_orig[3]);
848
849                                 //bl_debug_draw_quad_add(UNPACK4(quad_plane));
850                                 //bl_debug_draw_quad_add(UNPACK4(quad_orig));
851 #endif
852
853 #ifdef USE_ALTERNATE_ADJ
854                                 for (k = 1; k < ns; k++) {
855                                         float uv[2];
856                                         float fac;
857                                         float co_plane[3];
858                                         float co_orig[3];
859
860                                         get_point_uv(uv, v->ebev->seg, ring, k);
861                                         get_point_on_round_edge(uv, quad_plane, co_plane);
862                                         get_point_on_round_edge(uv, quad_orig,  co_orig);
863                                         fac = get_point_uv_factor(uv);
864                                         interp_v3_v3v3(co, co_plane, co_orig, fac);
865                                         copy_v3_v3(mesh_vert(vm, i, ring, k)->co, co);
866                                 }
867 #else
868                                 /* TODO: better calculation of new midarc point? */
869                                 project_to_edge(v->ebev->e, coa, cob, midco);
870
871                                 for (k = 1; k < ns; k++) {
872                                         get_point_on_round_edge(v->ebev, k, coa, midco, cob, co);
873                                         copy_v3_v3(mesh_vert(vm, i, ring, k)->co, co);
874                                 }
875 #endif
876                         }
877                 } while ((v = v->next) != vm->boundstart);
878         }
879
880         /* Now make sure cross points of rings share coordinates and vertices.
881          * After this loop, will have BMVerts for all (i, r, k) where
882          * i is for a BoundVert that is beveled and has either a predecessor or
883          * successor BoundVert beveled too, and
884          * for odd ns: 0 <= r <= ns2, 0 <= k <= ns
885          * for even ns: 0 <= r < ns2, 0 <= k <= ns except k=ns2 */
886         v = vm->boundstart;
887         do {
888                 i = v->index;
889                 if (v->ebev) {
890                         vprev = v->prev;
891                         vnext = v->next;
892                         if (vprev->ebev) {
893                                 for (ring = 1; ring <= ns2; ring++) {
894                                         for (k = 1; k <= ns2; k++) {
895                                                 if (ns % 2 == 0 && (k == ns2 || ring == ns2))
896                                                         continue;  /* center line is special case: do after the rest are done */
897                                                 nv = mesh_vert(vm, i, ring, k);
898                                                 nvprev = mesh_vert(vm, vprev->index, k, ns - ring);
899                                                 mid_v3_v3v3(co, nv->co, nvprev->co);
900 #ifndef USE_ALTERNATE_ADJ
901                                                 copy_v3_v3(nv->co, co);
902 #endif
903                                                 BLI_assert(nv->v == NULL && nvprev->v == NULL);
904                                                 create_mesh_bmvert(bm, vm, i, ring, k, bv->v);
905                                                 copy_mesh_vert(vm, vprev->index, k, ns - ring, i, ring, k);
906                                         }
907                                 }
908                                 if (!vprev->prev->ebev) {
909                                         for (ring = 1; ring <= ns2; ring++) {
910                                                 for (k = 1; k <= ns2; k++) {
911                                                         if (ns % 2 == 0 && (k == ns2 || ring == ns2))
912                                                                 continue;
913                                                         create_mesh_bmvert(bm, vm, vprev->index, ring, k, bv->v);
914                                                 }
915                                         }
916                                 }
917                                 if (!vnext->ebev) {
918                                         for (ring = 1; ring <= ns2; ring++) {
919                                                 for (k = ns - ns2; k < ns; k++) {
920                                                         if (ns % 2 == 0 && (k == ns2 || ring == ns2))
921                                                                 continue;
922                                                         create_mesh_bmvert(bm, vm, i, ring, k, bv->v);
923                                                 }
924                                         }
925                                 }
926                         }
927                 }
928         } while ((v = v->next) != vm->boundstart);
929
930         if (ns % 2 == 0) {
931                 /* Do special case center lines.
932                  * This loop makes verts for (i, ns2, k) for 1 <= k <= ns-1, k!=ns2
933                  * and for (i, r, ns2) for 1 <= r <= ns2-1,
934                  * whenever i is in a sequence of at least two beveled verts */
935                 v = vm->boundstart;
936                 do {
937                         i = v->index;
938                         if (v->ebev) {
939                                 vprev = v->prev;
940                                 vnext = v->next;
941                                 for (k = 1; k < ns2; k++) {
942                                         nv = mesh_vert(vm, i, k, ns2);
943                                         if (vprev->ebev)
944                                                 nvprev = mesh_vert(vm, vprev->index, ns2, ns - k);
945                                         if (vnext->ebev)
946                                                 nvnext = mesh_vert(vm, vnext->index, ns2, k);
947                                         if (vprev->ebev && vnext->ebev) {
948                                                 mid_v3_v3v3v3(co, nvprev->co, nv->co, nvnext->co);
949 #ifndef USE_ALTERNATE_ADJ
950                                                 copy_v3_v3(nv->co, co);
951 #endif
952                                                 create_mesh_bmvert(bm, vm, i, k, ns2, bv->v);
953                                                 copy_mesh_vert(vm, vprev->index, ns2, ns - k, i, k, ns2);
954                                                 copy_mesh_vert(vm, vnext->index, ns2, k, i, k, ns2);
955
956                                         }
957                                         else if (vprev->ebev) {
958                                                 mid_v3_v3v3(co, nvprev->co, nv->co);
959 #ifndef USE_ALTERNATE_ADJ
960                                                 copy_v3_v3(nv->co, co);
961 #endif
962                                                 create_mesh_bmvert(bm, vm, i, k, ns2, bv->v);
963                                                 copy_mesh_vert(vm, vprev->index, ns2, ns - k, i, k, ns2);
964
965                                                 create_mesh_bmvert(bm, vm, i, ns2, ns - k, bv->v);
966                                         }
967                                         else if (vnext->ebev) {
968                                                 mid_v3_v3v3(co, nv->co, nvnext->co);
969 #ifndef USE_ALTERNATE_ADJ
970                                                 copy_v3_v3(nv->co, co);
971 #endif
972                                                 create_mesh_bmvert(bm, vm, i, k, ns2, bv->v);
973                                                 copy_mesh_vert(vm, vnext->index, ns2, k, i, k, ns2);
974
975                                                 create_mesh_bmvert(bm, vm, i, ns2, k, bv->v);
976                                         }
977                                 }
978                         }
979                 } while ((v = v->next) != vm->boundstart);
980
981                 /* center point need to be average of all centers of rings */
982                 /* TODO: this is wrong if not all verts have ebev: could have
983                  * several disconnected sections of mesh. */
984                 zero_v3(midco);
985                 nn = 0;
986                 v = vm->boundstart;
987                 do {
988                         i = v->index;
989                         if (v->ebev) {
990                                 nv = mesh_vert(vm, i, ns2, ns2);
991                                 add_v3_v3(midco, nv->co);
992                                 nn++;
993                         }
994                 } while ((v = v->next) != vm->boundstart);
995                 mul_v3_fl(midco, 1.0f / nn);
996                 bmv = BM_vert_create(bm, midco, NULL);
997                 v = vm->boundstart;
998                 do {
999                         i = v->index;
1000                         if (v->ebev) {
1001                                 nv = mesh_vert(vm, i, ns2, ns2);
1002                                 copy_v3_v3(nv->co, midco);
1003                                 nv->v = bmv;
1004                         }
1005                 } while ((v = v->next) != vm->boundstart);
1006         }
1007
1008         /* Make the ring quads */
1009         for (ring = 0; ring < ns2; ring++) {
1010                 v = vm->boundstart;
1011                 do {
1012                         i = v->index;
1013                         f = boundvert_rep_face(v);
1014                         if (v->ebev && (v->prev->ebev || v->next->ebev)) {
1015                                 for (k = 0; k < ns2 + (ns % 2); k++) {
1016                                         bmv1 = mesh_vert(vm, i, ring, k)->v;
1017                                         bmv2 = mesh_vert(vm, i, ring, k + 1)->v;
1018                                         bmv3 = mesh_vert(vm, i, ring + 1, k + 1)->v;
1019                                         bmv4 = mesh_vert(vm, i, ring + 1, k)->v;
1020                                         BLI_assert(bmv1 && bmv2 && bmv3 && bmv4);
1021                                         if (bmv3 == bmv4 || bmv1 == bmv4)
1022                                                 bmv4 = NULL;
1023                                         bev_create_quad_tri(bm, bmv1, bmv2, bmv3, bmv4, f);
1024                                 }
1025                         }
1026                         else if (v->prev->ebev && v->prev->prev->ebev) {
1027                                 /* finish off a sequence of beveled edges */
1028                                 i = v->prev->index;
1029                                 f = boundvert_rep_face(v->prev);
1030                                 for (k = ns2 + (ns % 2); k < ns; k++) {
1031                                         bmv1 = mesh_vert(vm, i, ring, k)->v;
1032                                         bmv2 = mesh_vert(vm, i, ring, k + 1)->v;
1033                                         bmv3 = mesh_vert(vm, i, ring + 1, k + 1)->v;
1034                                         bmv4 = mesh_vert(vm, i, ring + 1, k)->v;
1035                                         BLI_assert(bmv1 && bmv2 && bmv3 && bmv4);
1036                                         if (bmv2 == bmv3) {
1037                                                 bmv3 = bmv4;
1038                                                 bmv4 = NULL;
1039                                         }
1040                                         bev_create_quad_tri(bm, bmv1, bmv2, bmv3, bmv4, f);
1041                                 }
1042                         }
1043                 } while ((v = v->next) != vm->boundstart);
1044         }
1045
1046         /* Make center ngon if odd number of segments and fully beveled */
1047         if (ns % 2 == 1 && vm->count == bv->selcount) {
1048                 BMVert **vv = NULL;
1049                 BLI_array_declare(vv);
1050
1051                 v = vm->boundstart;
1052                 do {
1053                         i = v->index;
1054                         BLI_assert(v->ebev);
1055                         BLI_array_append(vv, mesh_vert(vm, i, ns2, ns2)->v);
1056                 } while ((v = v->next) != vm->boundstart);
1057                 f = boundvert_rep_face(vm->boundstart);
1058                 bev_create_ngon(bm, vv, BLI_array_count(vv), f);
1059
1060                 BLI_array_free(vv);
1061         }
1062
1063         /* Make 'rest-of-vmesh' polygon if not fully beveled */
1064         if (vm->count > bv->selcount) {
1065                 int j;
1066                 BMVert **vv = NULL;
1067                 BLI_array_declare(vv);
1068
1069                 v = vm->boundstart;
1070                 f = boundvert_rep_face(v);
1071                 j = 0;
1072                 do {
1073                         i = v->index;
1074                         if (v->ebev) {
1075                                 if (!v->prev->ebev) {
1076                                         for (k = 0; k < ns2; k++) {
1077                                                 bmv1 = mesh_vert(vm, i, ns2, k)->v;
1078                                                 if (!bmv1)
1079                                                         bmv1 = mesh_vert(vm, i, 0, k)->v;
1080                                                 if (!(j > 0 && bmv1 == vv[j - 1])) {
1081                                                         BLI_assert(bmv1 != NULL);
1082                                                         BLI_array_append(vv, bmv1);
1083                                                         j++;
1084                                                 }
1085                                         }
1086                                 }
1087                                 bmv1 = mesh_vert(vm, i, ns2, ns2)->v;
1088                                 if (!bmv1)
1089                                         bmv1 = mesh_vert(vm, i, 0, ns2)->v;
1090                                 if (!(j > 0 && bmv1 == vv[j - 1])) {
1091                                         BLI_assert(bmv1 != NULL);
1092                                         BLI_array_append(vv, bmv1);
1093                                         j++;
1094                                 }
1095                                 if (!v->next->ebev) {
1096                                         for (k = ns - ns2; k < ns; k++) {
1097                                                 bmv1 = mesh_vert(vm, i, ns2, k)->v;
1098                                                 if (!bmv1)
1099                                                         bmv1 = mesh_vert(vm, i, 0, k)->v;
1100                                                 if (!(j > 0 && bmv1 == vv[j - 1])) {
1101                                                         BLI_assert(bmv1 != NULL);
1102                                                         BLI_array_append(vv, bmv1);
1103                                                         j++;
1104                                                 }
1105                                         }
1106                                 }
1107                         }
1108                         else {
1109                                 BLI_assert(mesh_vert(vm, i, 0, 0)->v != NULL);
1110                                 BLI_array_append(vv, mesh_vert(vm, i, 0, 0)->v);
1111                                 j++;
1112                         }
1113                 } while ((v = v->next) != vm->boundstart);
1114                 if (vv[0] == vv[j - 1])
1115                         j--;
1116                 bev_create_ngon(bm, vv, j, f);
1117
1118                 BLI_array_free(vv);
1119         }
1120 }
1121
1122 static BMFace *bevel_build_poly_ex(BMesh *bm, BevVert *bv)
1123 {
1124         BMFace *f;
1125         int n, k;
1126         VMesh *vm = bv->vmesh;
1127         BoundVert *v;
1128         BMVert **vv = NULL;
1129         BLI_array_declare(vv);
1130
1131         v = vm->boundstart;
1132         n = 0;
1133         do {
1134                 /* accumulate vertices for vertex ngon */
1135                 BLI_array_append(vv, v->nv.v);
1136                 n++;
1137                 if (v->ebev && v->ebev->seg > 1) {
1138                         for (k = 1; k < v->ebev->seg; k++) {
1139                                 BLI_array_append(vv, mesh_vert(vm, v->index, 0, k)->v);
1140                                 n++;
1141                         }
1142                 }
1143         } while ((v = v->next) != vm->boundstart);
1144         if (n > 2) {
1145                 f = bev_create_ngon(bm, vv, n, boundvert_rep_face(v));
1146         }
1147         else {
1148                 f = NULL;
1149         }
1150         BLI_array_free(vv);
1151         return f;
1152 }
1153
1154 static void bevel_build_poly(BMesh *bm, BevVert *bv)
1155 {
1156         bevel_build_poly_ex(bm, bv);
1157 }
1158
1159 static void bevel_build_trifan(BMesh *bm, BevVert *bv)
1160 {
1161         BMFace *f;
1162         BLI_assert(next_bev(bv, NULL)->seg == 1 || bv->selcount == 1);
1163
1164         f = bevel_build_poly_ex(bm, bv);
1165
1166         if (f) {
1167                 /* we have a polygon which we know starts at the previous vertex, make it into a fan */
1168                 BMLoop *l_fan = BM_FACE_FIRST_LOOP(f)->prev;
1169                 BMVert *v_fan = l_fan->v;
1170
1171                 while (f->len > 3) {
1172                         BMLoop *l_new;
1173                         BMFace *f_new;
1174                         BLI_assert(v_fan == l_fan->v);
1175                         f_new = BM_face_split(bm, f, l_fan->v, l_fan->next->next->v, &l_new, NULL, FALSE);
1176
1177                         if (f_new->len > f->len) {
1178                                 f = f_new;
1179                                 if      (l_new->v       == v_fan) { l_fan = l_new; }
1180                                 else if (l_new->next->v == v_fan) { l_fan = l_new->next; }
1181                                 else if (l_new->prev->v == v_fan) { l_fan = l_new->prev; }
1182                                 else { BLI_assert(0); }
1183                         }
1184                         else {
1185                                 if      (l_fan->v       == v_fan) { l_fan = l_fan; }
1186                                 else if (l_fan->next->v == v_fan) { l_fan = l_fan->next; }
1187                                 else if (l_fan->prev->v == v_fan) { l_fan = l_fan->prev; }
1188                                 else { BLI_assert(0); }
1189                         }
1190                 }
1191         }
1192 }
1193
1194 static void bevel_build_quadstrip(BMesh *bm, BevVert *bv)
1195 {
1196         BMFace *f;
1197         BLI_assert(bv->selcount == 2);
1198
1199         f = bevel_build_poly_ex(bm, bv);
1200
1201         if (f) {
1202                 /* we have a polygon which we know starts at this vertex, make it into strips */
1203                 EdgeHalf *eh_a = bv->vmesh->boundstart->elast;
1204                 EdgeHalf *eh_b = next_bev(bv, eh_a->next);  /* since (selcount == 2) we know this is valid */
1205                 BMLoop *l_a = BM_face_vert_share_loop(f, eh_a->rightv->nv.v);
1206                 BMLoop *l_b = BM_face_vert_share_loop(f, eh_b->leftv->nv.v);
1207                 int seg_count = bv->vmesh->seg;  /* ensure we don't walk past the segments */
1208
1209                 if (l_a == l_b) {
1210                         /* step once around if we hit the same loop */
1211                         l_a = l_a->prev;
1212                         l_b = l_b->next;
1213                         seg_count--;
1214                 }
1215
1216                 BLI_assert(l_a != l_b);
1217
1218                 while (f->len > 4) {
1219                         BMLoop *l_new;
1220                         BLI_assert(l_a->f == f);
1221                         BLI_assert(l_b->f == f);
1222
1223                         BM_face_split(bm, f, l_a->v, l_b->v, &l_new, NULL, FALSE);
1224                         if (seg_count-- == 0) {
1225                                 break;
1226                         }
1227
1228                         /* turns out we don't need this,
1229                          * because of how BM_face_split works we always get the loop of the next face */
1230 #if 0
1231                         if (l_new->f->len < l_new->radial_next->f->len) {
1232                                 l_new = l_new->radial_next;
1233                         }
1234 #endif
1235                         f = l_new->f;
1236
1237                         /* walk around the new face to get the next verts to split */
1238                         l_a = l_new->prev;
1239                         l_b = l_new->next->next;
1240                 }
1241         }
1242 }
1243
1244 /* Given that the boundary is built, now make the actual BMVerts
1245  * for the boundary and the interior of the vertex mesh. */
1246 static void build_vmesh(MemArena *mem_arena, BMesh *bm, BevVert *bv)
1247 {
1248         VMesh *vm = bv->vmesh;
1249         BoundVert *v, *weld1, *weld2;
1250         int n, ns, ns2, i, k, weld;
1251         float *va, *vb, co[3];
1252
1253 #ifdef USE_ALTERNATE_ADJ
1254         /* ordered as follows (orig, prev, center, next)*/
1255         float quad_plane[4][3];
1256         float quad_orig_a[4][3];
1257         float quad_orig_b[4][3];
1258         const int is_odd = (vm->seg % 2);
1259 #else
1260         float midco[3];
1261 #endif
1262
1263 #ifdef USE_ALTERNATE_ADJ
1264         /* the rest are initialized inline, this remains the same for all */
1265         /* NOTE; in this usage we only interpolate on the 'V' so cent and next points are unused (2,3)*/
1266         vmesh_cent(vm, quad_plane[2]);
1267         copy_v3_v3(quad_orig_a[2], bv->v->co);
1268         copy_v3_v3(quad_orig_b[2], bv->v->co);
1269 #endif
1270
1271         n = vm->count;
1272         ns = vm->seg;
1273         ns2 = ns / 2;
1274
1275         vm->mesh = (NewVert *)BLI_memarena_alloc(mem_arena, n * (ns2 + 1) * (ns + 1) * sizeof(NewVert));
1276
1277         /* special case: two beveled ends welded together */
1278         weld = (bv->selcount == 2) && (vm->count == 2);
1279         weld1 = weld2 = NULL;   /* will hold two BoundVerts involved in weld */
1280
1281         /* make (i, 0, 0) mesh verts for all i */
1282         v = vm->boundstart;
1283         do {
1284                 i = v->index;
1285                 copy_v3_v3(mesh_vert(vm, i, 0, 0)->co, v->nv.co);
1286                 create_mesh_bmvert(bm, vm, i, 0, 0, bv->v);
1287                 v->nv.v = mesh_vert(vm, i, 0, 0)->v;
1288                 if (weld && v->ebev) {
1289                         if (!weld1)
1290                                 weld1 = v;
1291                         else
1292                                 weld2 = v;
1293                 }
1294         } while ((v = v->next) != vm->boundstart);
1295
1296         /* copy other ends to (i, 0, ns) for all i, and fill in profiles for beveled edges */
1297         v = vm->boundstart;
1298         do {
1299                 i = v->index;
1300                 copy_mesh_vert(vm, i, 0, ns, v->next->index, 0, 0);
1301                 if (v->ebev) {
1302
1303 #ifdef USE_ALTERNATE_ADJ
1304                         copy_v3_v3(quad_plane[0], v->nv.co);
1305                         mid_v3_v3v3(quad_plane[1], v->nv.co, v->prev->nv.co);
1306                         /* quad[2] is set */
1307                         mid_v3_v3v3(quad_plane[3], v->nv.co, v->next->nv.co);
1308
1309                         /* orig 'A' */
1310                         copy_v3_v3(quad_orig_a[0], v->nv.co);  /* only shared location between 2 quads */
1311                         project_to_edge(v->ebev->prev->e, v->nv.co, v->prev->nv.co, quad_orig_a[1]);
1312                         project_to_edge(v->ebev->e,       v->nv.co, v->next->nv.co, quad_orig_a[3]);
1313
1314                         /* orig 'B' */
1315                         copy_v3_v3(quad_orig_b[3], v->next->nv.co);  /* only shared location between 2 quads */
1316                         project_to_edge(v->ebev->prev->e, v->nv.co, v->prev->nv.co, quad_orig_b[1]);
1317                         project_to_edge(v->ebev->e,       v->nv.co, v->next->nv.co, quad_orig_b[0]);
1318
1319                         //bl_debug_draw_quad_add(UNPACK4(quad_plane));
1320                         //bl_debug_draw_quad_add(UNPACK4(quad_orig_a));
1321                         //bl_debug_draw_quad_add(UNPACK4(quad_orig_b));
1322 #endif  /* USE_ALTERNATE_ADJ */
1323
1324 #ifdef USE_ALTERNATE_ADJ
1325                         for (k = 1; k < ns; k++) {
1326                                 float uv[2];
1327                                 float fac;
1328                                 float co_plane[3];
1329                                 float co_orig[3];
1330
1331                                 /* quad_plane */
1332                                 get_point_uv(uv, v->ebev->seg, 0, k);
1333                                 get_point_on_round_edge(uv, quad_plane, co_plane);
1334
1335                                 /* quad_orig */
1336                                 /* each half has different UV's */
1337                                 if (k <= ns2) {
1338                                         get_point_uv(uv, v->ebev->seg, 0, k);
1339                                         get_point_on_round_edge(uv, quad_orig_a, co_orig);
1340                                 }
1341                                 else {
1342                                         get_point_uv(uv, v->ebev->seg, 0, (k - ns2) - (is_odd ? 0.5f : 0.0f));
1343                                         get_point_on_round_edge(uv, quad_orig_b, co_orig);
1344                                         uv[1] = 1.0f - uv[1];  /* so we can get the factor */
1345                                 }
1346                                 fac = get_point_uv_factor(uv);
1347
1348                                 /* done. interp */
1349                                 interp_v3_v3v3(co, co_plane, co_orig, fac);
1350                                 copy_v3_v3(mesh_vert(vm, i, 0, k)->co, co);
1351                                 if (!weld)
1352                                         create_mesh_bmvert(bm, vm, i, 0, k, bv->v);
1353                         }
1354 #else  /* USE_ALTERNATE_ADJ */
1355                         va = mesh_vert(vm, i, 0, 0)->co;
1356                         vb = mesh_vert(vm, i, 0, ns)->co;
1357                         project_to_edge(v->ebev->e, va, vb, midco);
1358                         for (k = 1; k < ns; k++) {
1359                                 get_point_on_round_edge(v->ebev, k, va, midco, vb, co);
1360                                 copy_v3_v3(mesh_vert(vm, i, 0, k)->co, co);
1361                                 if (!weld)
1362                                         create_mesh_bmvert(bm, vm, i, 0, k, bv->v);
1363                         }
1364 #endif  /* !USE_ALTERNATE_ADJ */
1365                 }
1366         } while ((v = v->next) != vm->boundstart);
1367
1368         if (weld) {
1369                 vm->mesh_kind = M_NONE;
1370                 for (k = 1; k < ns; k++) {
1371                         va = mesh_vert(vm, weld1->index, 0, k)->co;
1372                         vb = mesh_vert(vm, weld2->index, 0, ns - k)->co;
1373                         mid_v3_v3v3(co, va, vb);
1374                         copy_v3_v3(mesh_vert(vm, weld1->index, 0, k)->co, co);
1375                         create_mesh_bmvert(bm, vm, weld1->index, 0, k, bv->v);
1376                 }
1377                 for (k = 1; k < ns; k++)
1378                         copy_mesh_vert(vm, weld2->index, 0, ns - k, weld1->index, 0, k);
1379         }
1380
1381         switch (vm->mesh_kind) {
1382                 case M_NONE:
1383                         /* do nothing */
1384                         break;
1385                 case M_POLY:
1386                         bevel_build_poly(bm, bv);
1387                         break;
1388                 case M_ADJ:
1389                         bevel_build_rings(bm, bv);
1390                         break;
1391                 case M_TRI_FAN:
1392                         bevel_build_trifan(bm, bv);
1393                         break;
1394                 case M_QUAD_STRIP:
1395                         bevel_build_quadstrip(bm, bv);
1396                         break;
1397         }
1398 }
1399
1400 /* take care, this flag isn't cleared before use, it just so happens that its not set */
1401 #define BM_BEVEL_EDGE_TAG_ENABLE(bme)  BM_elem_flag_enable(  (bme)->l, BM_ELEM_TAG)
1402 #define BM_BEVEL_EDGE_TAG_DISABLE(bme) BM_elem_flag_disable( (bme)->l, BM_ELEM_TAG)
1403 #define BM_BEVEL_EDGE_TAG_TEST(bme)    BM_elem_flag_test(    (bme)->l, BM_ELEM_TAG)
1404
1405 /*
1406  * Construction around the vertex
1407  */
1408 static void bevel_vert_construct(BMesh *bm, BevelParams *bp, BMVert *v)
1409 {
1410         BMEdge *bme;
1411         BevVert *bv;
1412         BMEdge *bme2, *unflagged_bme;
1413         BMFace *f;
1414         BMIter iter, iter2;
1415         EdgeHalf *e;
1416         int i, ntot, found_shared_face, ccw_test_sum;
1417         int nsel = 0;
1418
1419         /* Gather input selected edges.
1420          * Only bevel selected edges that have exactly two incident faces.
1421          */
1422
1423         BM_ITER_ELEM (bme, &iter, v, BM_EDGES_OF_VERT) {
1424                 if (BM_elem_flag_test(bme, BM_ELEM_TAG)) {
1425                         BLI_assert(BM_edge_is_manifold(bme));
1426                         nsel++;
1427                 }
1428         }
1429
1430         if (nsel == 0) {
1431                 /* signal this vert isn't being beveled */
1432                 BM_elem_flag_disable(v, BM_ELEM_TAG);
1433                 return;
1434         }
1435
1436         ntot = BM_vert_edge_count(v);
1437         bv = (BevVert *)BLI_memarena_alloc(bp->mem_arena, (sizeof(BevVert)));
1438         bv->v = v;
1439         bv->edgecount = ntot;
1440         bv->selcount = nsel;
1441         bv->edges = (EdgeHalf *)BLI_memarena_alloc(bp->mem_arena, ntot * sizeof(EdgeHalf));
1442         bv->vmesh = (VMesh *)BLI_memarena_alloc(bp->mem_arena, sizeof(VMesh));
1443         bv->vmesh->seg = bp->seg;
1444         BLI_ghash_insert(bp->vert_hash, v, bv);
1445
1446         /* add edges to bv->edges in order that keeps adjacent edges sharing
1447          * a face, if possible */
1448         i = 0;
1449         bme = v->e;
1450         BM_BEVEL_EDGE_TAG_ENABLE(bme);
1451         e = &bv->edges[0];
1452         e->e = bme;
1453         for (i = 0; i < ntot; i++) {
1454                 if (i > 0) {
1455                         /* find an unflagged edge bme2 that shares a face f with previous bme */
1456                         found_shared_face = 0;
1457                         unflagged_bme = NULL;
1458                         BM_ITER_ELEM (bme2, &iter, v, BM_EDGES_OF_VERT) {
1459                                 if (BM_BEVEL_EDGE_TAG_TEST(bme2))
1460                                         continue;
1461                                 if (!unflagged_bme)
1462                                         unflagged_bme = bme2;
1463                                 BM_ITER_ELEM (f, &iter2, bme2, BM_FACES_OF_EDGE) {
1464                                         if (BM_face_edge_share_loop(f, bme)) {
1465                                                 found_shared_face = 1;
1466                                                 break;
1467                                         }
1468                                 }
1469                                 if (found_shared_face)
1470                                         break;
1471                         }
1472                         e = &bv->edges[i];
1473                         if (found_shared_face) {
1474                                 e->e = bme2;
1475                                 e->fprev = f;
1476                                 bv->edges[i - 1].fnext = f;
1477                         }
1478                         else {
1479                                 e->e = unflagged_bme;
1480                         }
1481                 }
1482                 bme = e->e;
1483                 BM_BEVEL_EDGE_TAG_ENABLE(bme);
1484                 if (BM_elem_flag_test(bme, BM_ELEM_TAG)) {
1485                         e->is_bev = TRUE;
1486                         e->seg = bp->seg;
1487                 }
1488                 else {
1489                         e->is_bev = FALSE;
1490                         e->seg = 0;
1491                 }
1492                 e->is_rev = (bme->v2 == v);
1493                 e->offset = e->is_bev ? bp->offset : 0.0f;
1494         }
1495         /* find wrap-around shared face */
1496         BM_ITER_ELEM (f, &iter2, bme, BM_FACES_OF_EDGE) {
1497                 if (BM_face_edge_share_loop(f, bv->edges[0].e)) {
1498                         if (bv->edges[0].fnext == f)
1499                                 continue;   /* if two shared faces, want the other one now */
1500                         bv->edges[ntot - 1].fnext = f;
1501                         bv->edges[0].fprev = f;
1502                         break;
1503                 }
1504         }
1505
1506         /* clear BEVEL_EDGE_TAG now that we are finished with it*/
1507         for (i = 0; i < ntot; i++) {
1508                 BM_BEVEL_EDGE_TAG_DISABLE(bv->edges[i].e);
1509         }
1510
1511         /* if edge array doesn't go CCW around vertex from average normal side,
1512          * reverse the array, being careful to reverse face pointers too */
1513         if (ntot > 1) {
1514                 ccw_test_sum = 0;
1515                 for (i = 0; i < ntot; i++)
1516                         ccw_test_sum += bev_ccw_test(bv->edges[i].e, bv->edges[(i + 1) % ntot].e,
1517                                                      bv->edges[i].fnext);
1518                 if (ccw_test_sum < 0) {
1519                         for (i = 0; i <= (ntot / 2) - 1; i++) {
1520                                 SWAP(EdgeHalf, bv->edges[i], bv->edges[ntot - i - 1]);
1521                                 SWAP(BMFace *, bv->edges[i].fprev, bv->edges[i].fnext);
1522                                 SWAP(BMFace *, bv->edges[ntot - i - 1].fprev, bv->edges[ntot - i - 1].fnext);
1523                         }
1524                         if (ntot % 2 == 1) {
1525                                 i = ntot / 2;
1526                                 SWAP(BMFace *, bv->edges[i].fprev,  bv->edges[i].fnext);
1527                         }
1528                 }
1529         }
1530
1531         for (i = 0; i < ntot; i++) {
1532                 e = &bv->edges[i];
1533                 e->next = &bv->edges[(i + 1) % ntot];
1534                 e->prev = &bv->edges[(i + ntot - 1) % ntot];
1535         }
1536
1537         build_boundary(bp->mem_arena, bv);
1538         build_vmesh(bp->mem_arena, bm, bv);
1539 }
1540
1541 /* Face f has at least one beveled vertex.  Rebuild f */
1542 static int bev_rebuild_polygon(BMesh *bm, BevelParams *bp, BMFace *f)
1543 {
1544         BMIter liter;
1545         BMLoop *l, *lprev;
1546         BevVert *bv;
1547         BoundVert *v, *vstart, *vend;
1548         EdgeHalf *e, *eprev;
1549         VMesh *vm;
1550         int i, k;
1551         int do_rebuild = FALSE;
1552         BMVert *bmv;
1553         BMVert **vv = NULL;
1554         BLI_array_staticdeclare(vv, BM_DEFAULT_NGON_STACK_SIZE);
1555
1556         BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
1557                 bv = find_bevvert(bp, l->v);
1558                 if (bv) {
1559                         lprev = l->prev;
1560                         e = find_edge_half(bv, l->e);
1561                         eprev = find_edge_half(bv, lprev->e);
1562                         BLI_assert(e != NULL && eprev != NULL);
1563                         vstart = eprev->leftv;
1564                         if (e->is_bev)
1565                                 vend = e->rightv;
1566                         else
1567                                 vend = e->leftv;
1568                         v = vstart;
1569                         vm = bv->vmesh;
1570                         BLI_array_append(vv, v->nv.v);
1571                         while (v != vend) {
1572                                 if (vm->mesh_kind == M_NONE && v->ebev && v->ebev->seg > 1 && v->ebev != e && v->ebev != eprev) {
1573                                         /* case of 3rd face opposite a beveled edge, with no vmesh */
1574                                         i = v->index;
1575                                         e = v->ebev;
1576                                         for (k = 1; k < e->seg; k++) {
1577                                                 bmv = mesh_vert(vm, i, 0, k)->v;
1578                                                 BLI_array_append(vv, bmv);
1579                                         }
1580                                 }
1581                                 v = v->prev;
1582                                 BLI_array_append(vv, v->nv.v);
1583                         }
1584
1585                         do_rebuild = TRUE;
1586                 }
1587                 else {
1588                         BLI_array_append(vv, l->v);
1589                 }
1590         }
1591         if (do_rebuild) {
1592                 BMFace *f_new = bev_create_ngon(bm, vv, BLI_array_count(vv), f);
1593
1594                 /* don't select newly created boundary faces... */
1595                 if (f_new) {
1596                         BM_elem_flag_disable(f_new, BM_ELEM_TAG);
1597                 }
1598         }
1599
1600         BLI_array_free(vv);
1601         return do_rebuild;
1602 }
1603
1604 /* All polygons touching v need rebuilding because beveling v has made new vertices */
1605 static void bevel_rebuild_existing_polygons(BMesh *bm, BevelParams *bp, BMVert *v)
1606 {
1607         void    *faces_stack[BM_DEFAULT_ITER_STACK_SIZE];
1608         int      faces_len, f_index;
1609         BMFace **faces = BM_iter_as_arrayN(bm, BM_FACES_OF_VERT, v, &faces_len,
1610                                            faces_stack, BM_DEFAULT_ITER_STACK_SIZE);
1611
1612         if (LIKELY(faces != NULL)) {
1613                 for (f_index = 0; f_index < faces_len; f_index++) {
1614                         BMFace *f = faces[f_index];
1615                         if (bev_rebuild_polygon(bm, bp, f)) {
1616                                 BM_face_kill(bm, f);
1617                         }
1618                 }
1619
1620                 if (faces != (BMFace **)faces_stack) {
1621                         MEM_freeN(faces);
1622                 }
1623         }
1624 }
1625
1626
1627
1628 /*
1629  * Build the polygons along the selected Edge
1630  */
1631 static void bevel_build_edge_polygons(BMesh *bm, BevelParams *bp, BMEdge *bme)
1632 {
1633         BevVert *bv1, *bv2;
1634         BMVert *bmv1, *bmv2, *bmv3, *bmv4, *bmv1i, *bmv2i, *bmv3i, *bmv4i;
1635         VMesh *vm1, *vm2;
1636         EdgeHalf *e1, *e2;
1637         BMFace *f1, *f2, *f;
1638         int k, nseg, i1, i2;
1639
1640         if (!BM_edge_is_manifold(bme))
1641                 return;
1642
1643         bv1 = find_bevvert(bp, bme->v1);
1644         bv2 = find_bevvert(bp, bme->v2);
1645
1646         BLI_assert(bv1 && bv2);
1647
1648         e1 = find_edge_half(bv1, bme);
1649         e2 = find_edge_half(bv2, bme);
1650
1651         BLI_assert(e1 && e2);
1652
1653         /*   v4             v3
1654          *    \            /
1655          *     e->v1 - e->v2
1656          *    /            \
1657          *   v1             v2
1658          */
1659         nseg = e1->seg;
1660         BLI_assert(nseg > 0 && nseg == e2->seg);
1661
1662         bmv1 = e1->leftv->nv.v;
1663         bmv4 = e1->rightv->nv.v;
1664         bmv2 = e2->rightv->nv.v;
1665         bmv3 = e2->leftv->nv.v;
1666
1667         BLI_assert(bmv1 && bmv2 && bmv3 && bmv4);
1668
1669         f1 = boundvert_rep_face(e1->leftv);
1670         f2 = boundvert_rep_face(e1->rightv);
1671
1672         if (nseg == 1) {
1673                 bev_create_quad_tri(bm, bmv1, bmv2, bmv3, bmv4, f1);
1674         }
1675         else {
1676                 i1 = e1->leftv->index;
1677                 i2 = e2->leftv->index;
1678                 vm1 = bv1->vmesh;
1679                 vm2 = bv2->vmesh;
1680                 bmv1i = bmv1;
1681                 bmv2i = bmv2;
1682                 for (k = 1; k <= nseg; k++) {
1683                         bmv4i = mesh_vert(vm1, i1, 0, k)->v;
1684                         bmv3i = mesh_vert(vm2, i2, 0, nseg - k)->v;
1685                         f = (k <= nseg / 2 + (nseg % 2)) ? f1 : f2;
1686                         bev_create_quad_tri(bm, bmv1i, bmv2i, bmv3i, bmv4i, f);
1687                         bmv1i = bmv4i;
1688                         bmv2i = bmv3i;
1689                 }
1690         }
1691 }
1692
1693 /**
1694  * - Currently only bevels BM_ELEM_TAG'd verts and edges.
1695  *
1696  * - Newly created faces are BM_ELEM_TAG'd too,
1697  *   the caller needs to ensure this is cleared before calling
1698  *   if its going to use this face tag.
1699  *
1700  * \warning all tagged edges _must_ be manifold.
1701  */
1702 void BM_mesh_bevel(BMesh *bm, const float offset, const float segments)
1703 {
1704         BMIter iter;
1705         BMVert *v;
1706         BMEdge *e;
1707         BevelParams bp = {NULL};
1708
1709         bp.offset = offset;
1710         bp.seg    = segments;
1711
1712         if (bp.offset > 0) {
1713                 /* primary alloc */
1714                 bp.vert_hash = BLI_ghash_ptr_new(__func__);
1715                 bp.mem_arena = BLI_memarena_new((1 << 16), __func__);
1716                 BLI_memarena_use_calloc(bp.mem_arena);
1717
1718                 /* The analysis of the input vertices and execution additional constructions */
1719                 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
1720                         if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
1721                                 bevel_vert_construct(bm, &bp, v);
1722                         }
1723                 }
1724
1725                 /* Build polygons for edges */
1726                 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
1727                         if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
1728                                 bevel_build_edge_polygons(bm, &bp, e);
1729                         }
1730                 }
1731
1732                 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
1733                         if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
1734                                 bevel_rebuild_existing_polygons(bm, &bp, v);
1735                         }
1736                 }
1737
1738                 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
1739                         if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
1740                                 BLI_assert(find_bevvert(&bp, v) != NULL);
1741                                 BM_vert_kill(bm, v);
1742                         }
1743                 }
1744
1745                 /* primary free */
1746                 BLI_ghash_free(bp.vert_hash, NULL, NULL);
1747                 BLI_memarena_free(bp.mem_arena);
1748         }
1749 }