remove ifdef'd bevel code, current bevel works better then the previous code.
[blender.git] / source / blender / bmesh / operators / bmo_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): Joseph Eagar, Aleksandr Mokhov, Howard Trickey
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/bmesh/operators/bmo_bevel.c
24  *  \ingroup bmesh
25  */
26
27 #include "MEM_guardedalloc.h"
28
29 #include "BLI_listbase.h"
30 #include "BLI_array.h"
31 #include "BLI_math.h"
32 #include "BLI_smallhash.h"
33
34 #include "BKE_customdata.h"
35
36 #include "bmesh.h"
37
38 #include "intern/bmesh_operators_private.h" /* own include */
39
40 #define BEVEL_FLAG      1
41 #define EDGE_SELECTED   2
42
43 #define BEVEL_EPSILON  1e-6
44
45 /* Constructed vertex, sometimes later instantiated as BMVert */
46 typedef struct NewVert {
47         float co[3];
48         BMVert *v;
49 } NewVert;
50
51 struct BoundVert;
52
53 /* Data for one end of an edge involved in a bevel */
54 typedef struct EdgeHalf {
55         struct EdgeHalf *next, *prev;   /* in CCW order */
56         BMEdge *e;                  /* original mesh edge */
57         int isbev;                  /* is this edge beveled? */
58         int isrev;                  /* is e->v2 the vertex at this end? */
59         int seg;                    /* how many segments for the bevel */
60         float offset;               /* offset for this edge */
61         BMFace *fprev;              /* face between this edge and previous, if any */
62         BMFace *fnext;              /* face between this edge and next, if any */
63         struct BoundVert *leftv;    /* left boundary vert (looking along edge to end) */
64         struct BoundVert *rightv;   /* right boundary vert, if beveled */
65 } EdgeHalf;
66
67 /* An element in a cyclic boundary of a Vertex Mesh (VMesh) */
68 typedef struct BoundVert {
69         struct BoundVert *next, *prev;  /* in CCW order */
70         int index;          /* used for vmesh indexing */
71         NewVert nv;
72         EdgeHalf *efirst;   /* first of edges attached here: in CCW order */
73         EdgeHalf *elast;
74         EdgeHalf *ebev;     /* beveled edge whose left side is attached here, if any */
75 } BoundVert;
76
77 /* Mesh structure replacing a vertex */
78 typedef struct VMesh {
79         enum {
80                 M_NONE,         /* no polygon mesh needed */
81                 M_POLY,         /* a simple polygon */
82                 M_ADJ,          /* "adjacent edges" mesh pattern */
83                 M_CROSS,        /* "cross edges" mesh pattern */
84                 M_TRI_FAN,      /* a simple polygon - fan filled */
85                 M_QUAD_STRIP,   /* a simple polygon - cut into paralelle strips */
86         } mesh_kind;
87         int count;          /* number of vertices in the boundary */
88         int seg;            /* common # of segments for segmented edges */
89         BoundVert *boundstart;      /* start of boundary double-linked list */
90         NewVert *mesh;          /* allocated array - size and structure depends on kind */
91 } VMesh;
92
93 /* Data for a vertex involved in a bevel */
94 typedef struct BevVert {
95         struct BevVert *next, *prev;
96         BMVert *v;          /* original mesh vertex */
97         int edgecount;          /* total number of edges around the vertex */
98         int selcount;           /* number of selected edges around the vertex */
99         EdgeHalf *edges;        /* array of size edgecount; CCW order from vertex normal side */
100         VMesh *vmesh;           /* mesh structure for replacing vertex */
101 } BevVert;
102
103 /*
104  * Bevel parameters and state
105  */
106 typedef struct BevelParams {
107         ListBase vertList;      /* list of BevVert for each vertex involved in bevel */
108         float offset;           /* blender units to offset each side of a beveled edge */
109         int seg;                /* number of segments in beveled edge profile */
110
111         BMOperator *op;
112 } BevelParams;
113
114 /* Make a new BoundVert of the given kind, insert it at the end of the circular linked
115  * list with entry point bv->boundstart, and return it. */
116 static BoundVert *add_new_bound_vert(VMesh *vm, float co[3])
117 {
118         BoundVert *ans = (BoundVert *) MEM_callocN(sizeof(BoundVert), "BoundVert");
119         copy_v3_v3(ans->nv.co, co);
120         if (!vm->boundstart) {
121                 ans->index = 0;
122                 vm->boundstart = ans;
123                 ans->next = ans->prev = ans;
124         }
125         else {
126                 BoundVert *tail = vm->boundstart->prev;
127                 ans->index = tail->index + 1;
128                 ans->prev = tail;
129                 ans->next = vm->boundstart;
130                 tail->next = ans;
131                 vm->boundstart->prev = ans;
132         }
133         vm->count++;
134         return ans;
135 }
136
137 /* Mesh verts are indexed (i, j, k) where
138  * i = boundvert index (0 <= i < nv)
139  * j = ring index (0 <= j <= ns2)
140  * k = segment index (0 <= k <= ns)
141  * Not all of these are used, and some will share BMVerts */
142 static NewVert *mesh_vert(VMesh *vm, int i, int j, int k)
143 {
144         int nj = (vm->seg / 2) + 1;
145         int nk = vm->seg + 1;
146
147         return &vm->mesh[i * nk * nj  + j * nk + k];
148 }
149
150 static void create_mesh_bmvert(BMesh *bm, VMesh *vm, int i, int j, int k, BMVert *eg)
151 {
152         NewVert *nv = mesh_vert(vm, i, j, k);
153         nv->v = BM_vert_create(bm, nv->co, eg);
154 }
155
156 static void copy_mesh_vert(VMesh *vm, int ito, int jto, int kto,
157                            int ifrom, int jfrom, int kfrom)
158 {
159         NewVert *nvto, *nvfrom;
160
161         nvto = mesh_vert(vm, ito, jto, kto);
162         nvfrom = mesh_vert(vm, ifrom, jfrom, kfrom);
163         nvto->v = nvfrom->v;
164         copy_v3_v3(nvto->co, nvfrom->co);
165 }
166
167 /* find the EdgeHalf in bv's array that has edge bme */
168 static EdgeHalf *find_edge_half(BevVert *bv, BMEdge *bme)
169 {
170         int i;
171
172         for (i = 0; i < bv->edgecount; i++) {
173                 if (bv->edges[i].e == bme)
174                         return &bv->edges[i];
175         }
176         return NULL;
177 }
178
179 /* Return the next EdgeHalf after from_e that is beveled.
180  * If from_e is NULL, find the first beveled edge. */
181 static EdgeHalf *next_bev(BevVert *bv, EdgeHalf *from_e)
182 {
183         EdgeHalf *e;
184
185         if (from_e == NULL)
186                 from_e = &bv->edges[bv->edgecount - 1];
187         e = from_e;
188         do {
189                 if (e->isbev) {
190                         return e;
191                 }
192         } while ((e = e->next) != from_e);
193         return NULL;
194 }
195
196 /* find the BevVert corresponding to BMVert bmv */
197 static BevVert *find_bevvert(BevelParams *bp, BMVert *bmv)
198 {
199         BevVert *bv;
200
201         for (bv = bp->vertList.first; bv; bv = bv->next) {
202                 if (bv->v == bmv)
203                         return bv;
204         }
205         return NULL;
206 }
207
208 /* Return a good respresentative face (for materials, etc.) for faces
209  * created around/near BoundVert v */
210 static BMFace *boundvert_rep_face(BoundVert *v)
211 {
212         BMFace *fans = NULL;
213         BMFace *firstf = NULL;
214         BMEdge *e1, *e2;
215         BMFace *f1, *f2;
216         BMIter iter1, iter2;
217
218         BLI_assert(v->efirst != NULL && v->elast != NULL);
219         e1 = v->efirst->e;
220         e2 = v->elast->e;
221         BM_ITER_ELEM (f1, &iter1, e1, BM_FACES_OF_EDGE) {
222                 if (!firstf)
223                         firstf = f1;
224                 BM_ITER_ELEM (f2, &iter2, e2, BM_FACES_OF_EDGE) {
225                         if (f1 == f2) {
226                                 fans = f1;
227                                 break;
228                         }
229                 }
230         }
231         if (!fans)
232                 fans = firstf;
233
234         return fans;
235 }
236
237 /* Make ngon from verts alone.
238  * Make sure to properly copy face attributes and do custom data interpolation from
239  * example face, facerep. */
240 static BMFace *bev_create_ngon(BMesh *bm, BMVert **vert_arr, int totv, BMFace *facerep)
241 {
242         BMIter iter;
243         BMLoop *l;
244         BMFace *f;
245
246         if (totv == 3) {
247                 f = BM_face_create_quad_tri(bm,
248                                             vert_arr[0], vert_arr[1], vert_arr[2], NULL, facerep, 0);
249         }
250         else if (totv == 4) {
251                 f = BM_face_create_quad_tri(bm,
252                                             vert_arr[0], vert_arr[1], vert_arr[2], vert_arr[3], facerep, 0);
253         }
254         else {
255                 int i;
256                 BMEdge *e;
257                 BMEdge **ee = NULL;
258                 BLI_array_staticdeclare(ee, 30);
259
260                 for (i = 0; i < totv; i++) {
261                         e = BM_edge_create(bm, vert_arr[i], vert_arr[(i + 1) % totv], NULL, TRUE);
262                         BLI_array_append(ee, e);
263                 }
264                 f = BM_face_create_ngon(bm, vert_arr[0], vert_arr[1], ee, totv, FALSE);
265                 BLI_array_free(ee);
266         }
267         if (facerep && f) {
268                 int has_mdisps = CustomData_has_layer(&bm->ldata, CD_MDISPS);
269                 BM_elem_attrs_copy(bm, bm, facerep, f);
270                 BM_ITER_ELEM (l, &iter, f, BM_LOOPS_OF_FACE) {
271                         BM_loop_interp_from_face(bm, l, facerep, TRUE, TRUE);
272                         if (has_mdisps)
273                                 BM_loop_interp_multires(bm, l, facerep);
274                 }
275         }
276         return f;
277 }
278
279 static BMFace *bev_create_quad_tri(BMesh *bm, BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4,
280                                    BMFace *facerep)
281 {
282         BMVert *varr[4];
283
284         varr[0] = v1;
285         varr[1] = v2;
286         varr[2] = v3;
287         varr[3] = v4;
288         return bev_create_ngon(bm, varr, v4 ? 4 : 3, facerep);
289 }
290
291 /*
292  * Calculate the meeting point between the offset edges for e1 and e2, putting answer in meetco.
293  * e1 and e2 share vertex v and face f (may be NULL) and viewed from the normal side of
294  * the bevel vertex,  e1 precedes e2 in CCW order.
295  * If on_right is true, offset edge is on right of both edges, where e1 enters v and
296  * e2 leave it. If on_right is false, then the offset edge is on the left.
297  * When offsets are equal, the new point is on the edge bisector, with length offset/sin(angle/2),
298  * but if the offsets are not equal (allowing for this, as bevel modifier has edge weights that may
299  * lead to different offsets) then meeting point can be found be intersecting offset lines.
300  */
301 static void offset_meet(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, BMFace *f,
302                         int on_right, float meetco[3])
303 {
304         float dir1[3], dir2[3], norm_v[3], norm_perp1[3], norm_perp2[3],
305               off1a[3], off1b[3], off2a[3], off2b[3], isect2[3];
306
307         /* get direction vectors for two offset lines */
308         sub_v3_v3v3(dir1, v->co, BM_edge_other_vert(e1->e, v)->co);
309         sub_v3_v3v3(dir2, BM_edge_other_vert(e2->e, v)->co, v->co);
310
311         /* get normal to plane where meet point should be */
312         cross_v3_v3v3(norm_v, dir2, dir1);
313         normalize_v3(norm_v);
314         if (!on_right)
315                 negate_v3(norm_v);
316         if (is_zero_v3(norm_v)) {
317                 /* special case: e1 and e2 are parallel; put offset point perp to both, from v.
318                  * need to find a suitable plane.
319                  * if offsets are different, we're out of luck: just use e1->offset */
320                 if (f)
321                         copy_v3_v3(norm_v, f->no);
322                 else
323                         copy_v3_v3(norm_v, v->no);
324                 cross_v3_v3v3(norm_perp1, dir1, norm_v);
325                 normalize_v3(norm_perp1);
326                 copy_v3_v3(off1a, v->co);
327                 madd_v3_v3fl(off1a, norm_perp1, e1->offset);
328                 copy_v3_v3(meetco, off1a);
329         }
330         else {
331                 /* get vectors perp to each edge, perp to norm_v, and pointing into face */
332                 if (f) {
333                         copy_v3_v3(norm_v, f->no);
334                         normalize_v3(norm_v);
335                 }
336                 cross_v3_v3v3(norm_perp1, dir1, norm_v);
337                 cross_v3_v3v3(norm_perp2, dir2, norm_v);
338                 normalize_v3(norm_perp1);
339                 normalize_v3(norm_perp2);
340
341                 /* get points that are offset distances from each line, then another point on each line */
342                 copy_v3_v3(off1a, v->co);
343                 madd_v3_v3fl(off1a, norm_perp1, e1->offset);
344                 add_v3_v3v3(off1b, off1a, dir1);
345                 copy_v3_v3(off2a, v->co);
346                 madd_v3_v3fl(off2a, norm_perp2, e2->offset);
347                 add_v3_v3v3(off2b, off2a, dir2);
348
349                 /* intersect the lines; by construction they should be on the same plane and not parallel */
350                 if (!isect_line_line_v3(off1a, off1b, off2a, off2b, meetco, isect2)) {
351                         BLI_assert(!"offset_meet failure");
352                         copy_v3_v3(meetco, off1a);  /* just to do something */
353                 }
354         }
355 }
356
357 /* Like offset_meet, but here f1 and f2 must not be NULL and give the
358  * planes in which to run the offset lines.  They may not meet exactly,
359  * but the line intersection routine will find the closest approach point. */
360 static void offset_in_two_planes(EdgeHalf *e1, EdgeHalf *e2, BMVert *v,
361                                  BMFace *f1, BMFace *f2, float meetco[3])
362 {
363         float dir1[3], dir2[3], norm_perp1[3], norm_perp2[3],
364               off1a[3], off1b[3], off2a[3], off2b[3], isect2[3];
365
366         BLI_assert(f1 != NULL && f2 != NULL);
367
368         /* get direction vectors for two offset lines */
369         sub_v3_v3v3(dir1, v->co, BM_edge_other_vert(e1->e, v)->co);
370         sub_v3_v3v3(dir2, BM_edge_other_vert(e2->e, v)->co, v->co);
371
372         /* get directions into offset planes */
373         cross_v3_v3v3(norm_perp1, dir1, f1->no);
374         normalize_v3(norm_perp1);
375         cross_v3_v3v3(norm_perp2, dir2, f2->no);
376         normalize_v3(norm_perp2);
377
378         /* get points that are offset distances from each line, then another point on each line */
379         copy_v3_v3(off1a, v->co);
380         madd_v3_v3fl(off1a, norm_perp1, e1->offset);
381         add_v3_v3v3(off1b, off1a, dir1);
382         copy_v3_v3(off2a, v->co);
383         madd_v3_v3fl(off2a, norm_perp2, e2->offset);
384         add_v3_v3v3(off2b, off2a, dir2);
385
386         if (!isect_line_line_v3(off1a, off1b, off2a, off2b, meetco, isect2)) {
387                 /* lines are parallel; off1a is a good meet point */
388                 copy_v3_v3(meetco, off1a);
389         }
390 }
391
392 /* Offset by e->offset in plane with normal plane_no, on left if left==TRUE,
393  * else on right.  If no is NULL, choose an arbitrary plane different
394  * from eh's direction. */
395 static void offset_in_plane(EdgeHalf *e, float plane_no[3], int left, float r[3])
396 {
397         float dir[3], no[3];
398         BMVert *v;
399
400         v = e->isrev ? e->e->v1 : e->e->v2;
401
402         sub_v3_v3v3(dir, BM_edge_other_vert(e->e, v)->co, v->co);
403         normalize_v3(dir);
404         if (plane_no) {
405                 copy_v3_v3(no, plane_no);
406         }
407         else {
408                 zero_v3(no);
409                 if (fabs(dir[0]) < fabs(dir[1]))
410                         no[0] = 1.0f;
411                 else
412                         no[1] = 1.0f;
413         }
414         if (left)
415                 cross_v3_v3v3(r, no, dir);
416         else
417                 cross_v3_v3v3(r, dir, no);
418         normalize_v3(r);
419         mul_v3_fl(r, e->offset);
420 }
421
422 /* Calculate coordinates of a point a distance d from v on e->e and return it in slideco */
423 static void slide_dist(EdgeHalf *e, BMVert *v, float d, float slideco[3])
424 {
425         float dir[3], len;
426
427         sub_v3_v3v3(dir, v->co, BM_edge_other_vert(e->e, v)->co);
428         len = len_v3(dir);
429         normalize_v3(dir);
430         if (d > len)
431                 d = len - (float)(50 * BEVEL_EPSILON);
432         copy_v3_v3(slideco, v->co);
433         madd_v3_v3fl(slideco, dir, -d);
434 }
435
436 /* Calculate the point on e where line (co_a, co_b) comes closest to and return it in projco */
437 static void project_to_edge(BMEdge *e, float co_a[3], float co_b[3], float projco[3])
438 {
439         float otherco[3];
440
441         if (!isect_line_line_v3(e->v1->co, e->v2->co, co_a, co_b, projco, otherco)) {
442                 BLI_assert(!"project meet failure");
443                 copy_v3_v3(projco, e->v1->co);
444         }
445 }
446
447
448 /* return 1 if a and b are in CCW order on the normal side of f,
449  * and -1 if they are reversed, and 0 if there is no shared face f */
450 static int bev_ccw_test(BMEdge *a, BMEdge *b, BMFace *f)
451 {
452         BMLoop *la, *lb;
453
454         if (!f)
455                 return 0;
456         la = BM_face_edge_share_loop(f, a);
457         lb = BM_face_edge_share_loop(f, b);
458         if (!la || !lb)
459                 return 0;
460         return lb->next == la ? 1 : -1;
461 }
462
463 /*
464  * calculation of points on the round profile
465  * r - result, coordinate of point on round profile
466  * method:
467  * Inscribe a circle in angle va - v -vb
468  * such that it touches the arms at offset from v.
469  * Rotate the center-va segment by (i/n) of the
470  * angle va - center -vb, and put the endpoint
471  * of that segment in r.
472  */
473 static void get_point_on_round_profile(float r[3], float offset, int i, int count,
474                                        float va[3], float v[3], float vb[3])
475 {
476         float vva[3], vvb[3], angle, center[3], rv[3], axis[3], co[3];
477
478         sub_v3_v3v3(vva, va, v);
479         sub_v3_v3v3(vvb, vb, v);
480         normalize_v3(vva);
481         normalize_v3(vvb);
482         angle = angle_v3v3(vva, vvb);
483
484         add_v3_v3v3(center, vva, vvb);
485         normalize_v3(center);
486         mul_v3_fl(center, offset * (1.0f / cosf(0.5f * angle)));
487         add_v3_v3(center, v);           /* coordinates of the center of the inscribed circle */
488
489
490         sub_v3_v3v3(rv, va, center);    /* radius vector */
491
492
493         sub_v3_v3v3(co, v, center);
494         cross_v3_v3v3(axis, rv, co);    /* calculate axis */
495
496         sub_v3_v3v3(vva, va, center);
497         sub_v3_v3v3(vvb, vb, center);
498         angle = angle_v3v3(vva, vvb);
499
500         rotate_v3_v3v3fl(co, rv, axis, angle * (float)(i) / (float)(count));
501
502         add_v3_v3(co, center);
503         copy_v3_v3(r, co);
504 }
505
506 /*
507  * Find the point (i/n) of the way around the round profile for e,
508  * where start point is va, midarc point is vmid, and end point is vb.
509  * Return the answer in profileco.
510  * Method:
511  * Adjust va and vb (along edge direction) so that they are perpendicular
512  * to edge at v, then use get_point_on_round_profile, then project
513  * back onto original va - vmid - vb plane.
514  * If va, vmid, and vb are all on the same plane, just interpolate between va and vb.
515  */
516 static void get_point_on_round_edge(EdgeHalf *e, int i,
517                                     float va[3], float vmid[3], float vb[3], float profileco[3])
518 {
519         float vva[3], vvb[3],  point[3], dir[3], vaadj[3], vbadj[3], p2[3], pn[3];
520         int n = e->seg;
521
522         sub_v3_v3v3(vva, va, vmid);
523         sub_v3_v3v3(vvb, vb, vmid);
524         if (e->isrev)
525                 sub_v3_v3v3(dir, e->e->v1->co, e->e->v2->co);
526         else
527                 sub_v3_v3v3(dir, e->e->v2->co, e->e->v1->co);
528         normalize_v3(dir);
529         if (fabsf(angle_v3v3(vva, vvb) - (float)M_PI) > (float)BEVEL_EPSILON) {
530                 copy_v3_v3(vaadj, va);
531                 madd_v3_v3fl(vaadj, dir, -len_v3(vva) * cosf(angle_v3v3(vva, dir)));
532                 copy_v3_v3(vbadj, vb);
533                 madd_v3_v3fl(vbadj, dir, -len_v3(vvb) * cosf(angle_v3v3(vvb, dir)));
534
535                 get_point_on_round_profile(point, e->offset, i, n, vaadj, vmid, vbadj);
536
537                 add_v3_v3v3(p2, point, dir);
538                 cross_v3_v3v3(pn, vva, vvb);
539                 if (!isect_line_plane_v3(profileco, point, p2, vmid, pn, 0)) {
540                         /* TODO: track down why this sometimes fails */
541                         copy_v3_v3(profileco, point);
542                 }
543         }
544         else {
545                 /* planar case */
546                 interp_v3_v3v3(profileco, va, vb, (float) i / (float) n);
547         }
548 }
549
550 static void mid_v3_v3v3v3(float v[3], const float v1[3], const float v2[3], const float v3[3])
551 {
552         v[0] = (v1[0] + v2[0] + v3[0]) / 3.0f;
553         v[1] = (v1[1] + v2[1] + v3[1]) / 3.0f;
554         v[2] = (v1[2] + v2[2] + v3[2]) / 3.0f;
555 }
556
557 /* Make a circular list of BoundVerts for bv, each of which has the coordinates
558  * of a vertex on the the boundary of the beveled vertex bv->v.
559  * Also decide on the mesh pattern that will be used inside the boundary.
560  * Doesn't make the actual BMVerts */
561 static void build_boundary(BevVert *bv)
562 {
563         EdgeHalf *efirst, *e;
564         BoundVert *v;
565         VMesh *vm;
566         float co[3], *no;
567         float lastd;
568
569         e = efirst = next_bev(bv, NULL);
570         vm = bv->vmesh;
571
572         BLI_assert(bv->edgecount >= 2);  /* since bevel edges incident to 2 faces */
573
574         if (bv->edgecount == 2 && bv->selcount == 1) {
575                 /* special case: beveled edge meets non-beveled one at valence 2 vert */
576                 no = e->fprev ? e->fprev->no : (e->fnext ? e->fnext->no : NULL);
577                 offset_in_plane(e, no, TRUE, co);
578                 v = add_new_bound_vert(vm, co);
579                 v->efirst = v->elast = v->ebev = e;
580                 e->leftv = v;
581                 no = e->fnext ? e->fnext->no : (e->fprev ? e->fprev->no : NULL);
582                 offset_in_plane(e, no, FALSE, co);
583                 v = add_new_bound_vert(vm, co);
584                 v->efirst = v->elast = e;
585                 e->rightv = v;
586                 /* make artifical extra point along unbeveled edge, and form triangle */
587                 slide_dist(e->next, bv->v, e->offset, co);
588                 v = add_new_bound_vert(vm, co);
589                 v->efirst = v->elast = e->next;
590                 vm->mesh_kind = M_POLY;
591                 return;
592         }
593
594         lastd = e->offset;
595         vm->boundstart = NULL;
596         do {
597                 if (e->isbev) {
598                         /* handle only left side of beveled edge e here: next iteration should do right side */
599                         if (e->prev->isbev) {
600                                 BLI_assert(e->prev != e);  /* see: wire edge special case */
601                                 offset_meet(e->prev, e, bv->v, e->fprev, TRUE, co);
602                                 v = add_new_bound_vert(vm, co);
603                                 v->efirst = e->prev;
604                                 v->elast = v->ebev = e;
605                                 e->leftv = v;
606                                 e->prev->rightv = v;
607                         }
608                         else {
609                                 /* e->prev is not beveled */
610                                 if (e->prev->prev->isbev) {
611                                         BLI_assert(e->prev->prev != e); /* see: edgecount 2, selcount 1 case */
612                                         /* find meet point between e->prev->prev and e and attach e->prev there */
613                                         /* TODO: fix case when one or both faces in following are NULL */
614                                         offset_in_two_planes(e->prev->prev, e, bv->v,
615                                                              e->prev->prev->fnext, e->fprev, co);
616                                         v = add_new_bound_vert(vm, co);
617                                         v->efirst = e->prev->prev;
618                                         v->elast = v->ebev = e;
619                                         e->leftv = v;
620                                         e->prev->leftv = v;
621                                         e->prev->prev->rightv = v;
622                                 }
623                                 else {
624                                         /* neither e->prev nor e->prev->prev are beveled: make on-edge on e->prev */
625                                         offset_meet(e->prev, e, bv->v, e->fprev, TRUE, co);
626                                         v = add_new_bound_vert(vm, co);
627                                         v->efirst = e->prev;
628                                         v->elast = v->ebev = e;
629                                         e->leftv = v;
630                                         e->prev->leftv = v;
631                                 }
632                         }
633                         lastd = len_v3v3(bv->v->co, v->nv.co);
634                 }
635                 else {
636                         /* e is not beveled */
637                         if (e->next->isbev) {
638                                 /* next iteration will place e between beveled previous and next edges */
639                                 /* do nothing... */
640                         }
641                         else if (e->prev->isbev) {
642                                 /* on-edge meet between e->prev and e */
643                                 offset_meet(e->prev, e, bv->v, e->fprev, TRUE, co);
644                                 v = add_new_bound_vert(vm, co);
645                                 v->efirst = e->prev;
646                                 v->elast = e;
647                                 e->leftv = v;
648                                 e->prev->rightv = v;
649                         }
650                         else {
651                                 /* None of e->prev, e, e->next are beveled.
652                                  * could either leave alone or add slide points to make
653                                  * one polygon around bv->v.  For now, we choose latter.
654                                  * Could slide to make an even bevel plane but for now will
655                                  * just use last distance a meet point moved from bv->v. */
656                                 slide_dist(e, bv->v, lastd, co);
657                                 v = add_new_bound_vert(vm, co);
658                                 v->efirst = v->elast = e;
659                                 e->leftv = v;
660                         }
661                 }
662         } while ((e = e->next) != efirst);
663
664         BLI_assert(vm->count >= 2);
665         if (vm->count == 2 && bv->edgecount == 3) {
666                 vm->mesh_kind = M_NONE;
667         }
668         else if (efirst->seg == 1 || bv->selcount == 1) {
669                 if (vm->count == 3 && bv->selcount == 1) {
670                         vm->mesh_kind = M_TRI_FAN;
671                 }
672                 else {
673                         vm->mesh_kind = M_POLY;
674                 }
675         }
676         else {
677                 if (bv->selcount == 2) {
678                         vm->mesh_kind = M_QUAD_STRIP;
679                 }
680                 else {
681                         vm->mesh_kind = M_ADJ;
682                 }
683         }
684         /* TODO: if vm->count == 4 and bv->selcount == 4, use M_CROSS pattern */
685 }
686
687 /*
688  * Given that the boundary is built and the boundary BMVerts have been made,
689  * calculate the positions of the interior mesh points for the M_ADJ pattern,
690  * then make the BMVerts and the new faces. */
691 static void bevel_build_rings(BMesh *bm, BevVert *bv)
692 {
693         int k, ring, i, n, ns, ns2, nn;
694         VMesh *vm = bv->vmesh;
695         BoundVert *v, *vprev, *vnext;
696         NewVert *nv, *nvprev, *nvnext;
697         BMVert *bmv, *bmv1, *bmv2, *bmv3, *bmv4;
698         BMFace *f;
699         float co[3], coa[3], cob[3], midco[3];
700
701         n = vm->count;
702         ns = vm->seg;
703         ns2 = ns / 2;
704         BLI_assert(n > 2 && ns > 1);
705         /* Make initial rings, going between points on neighbors.
706          * After this loop, will have coords for all (i, r, k) where
707          * BoundVert for i has a bevel, 0 <= r <= ns2, 0 <= k <= ns */
708         for (ring = 1; ring <= ns2; ring++) {
709                 v = vm->boundstart;
710                 do {
711                         i = v->index;
712                         if (v->ebev) {
713                                 /* get points coords of points a and b, on outer rings
714                                  * of prev and next edges, k away from this edge */
715                                 vprev = v->prev;
716                                 vnext = v->next;
717
718                                 if (vprev->ebev)
719                                         nvprev = mesh_vert(vm, vprev->index, 0, ns - ring);
720                                 else
721                                         nvprev = mesh_vert(vm, vprev->index, 0, ns);
722                                 copy_v3_v3(coa, nvprev->co);
723                                 nv = mesh_vert(vm, i, ring, 0);
724                                 copy_v3_v3(nv->co, coa);
725                                 nv->v = nvprev->v;
726
727                                 if (vnext->ebev)
728                                         nvnext = mesh_vert(vm, vnext->index, 0, ring);
729                                 else
730                                         nvnext = mesh_vert(vm, vnext->index, 0, 0);
731                                 copy_v3_v3(cob, nvnext->co);
732                                 nv = mesh_vert(vm, i, ring, ns);
733                                 copy_v3_v3(nv->co, cob);
734                                 nv->v = nvnext->v;
735
736                                 /* TODO: better calculation of new midarc point? */
737                                 project_to_edge(v->ebev->e, coa, cob, midco);
738
739                                 for (k = 1; k < ns; k++) {
740                                         get_point_on_round_edge(v->ebev, k, coa, midco, cob, co);
741                                         copy_v3_v3(mesh_vert(vm, i, ring, k)->co, co);
742                                 }
743                         }
744                 } while ((v = v->next) != vm->boundstart);
745         }
746
747         /* Now make sure cross points of rings share coordinates and vertices.
748          * After this loop, will have BMVerts for all (i, r, k) where
749          * i is for a BoundVert that is beveled and has either a predecessor or
750          * successor BoundVert beveled too, and
751          * for odd ns: 0 <= r <= ns2, 0 <= k <= ns
752          * for even ns: 0 <= r < ns2, 0 <= k <= ns except k=ns2 */
753         v = vm->boundstart;
754         do {
755                 i = v->index;
756                 if (v->ebev) {
757                         vprev = v->prev;
758                         vnext = v->next;
759                         if (vprev->ebev) {
760                                 for (ring = 1; ring <= ns2; ring++) {
761                                         for (k = 1; k <= ns2; k++) {
762                                                 if (ns % 2 == 0 && (k == ns2 || ring == ns2))
763                                                         continue;  /* center line is special case: do after the rest are done */
764                                                 nv = mesh_vert(vm, i, ring, k);
765                                                 nvprev = mesh_vert(vm, vprev->index, k, ns - ring);
766                                                 mid_v3_v3v3(co, nv->co, nvprev->co);
767                                                 copy_v3_v3(nv->co, co);
768                                                 BLI_assert(nv->v == NULL && nvprev->v == NULL);
769                                                 create_mesh_bmvert(bm, vm, i, ring, k, bv->v);
770                                                 copy_mesh_vert(vm, vprev->index, k, ns - ring, i, ring, k);
771                                         }
772                                 }
773                                 if (!vprev->prev->ebev) {
774                                         for (ring = 1; ring <= ns2; ring++) {
775                                                 for (k = 1; k <= ns2; k++) {
776                                                         if (ns % 2 == 0 && (k == ns2 || ring == ns2))
777                                                                 continue;
778                                                         create_mesh_bmvert(bm, vm, vprev->index, ring, k, bv->v);
779                                                 }
780                                         }
781                                 }
782                                 if (!vnext->ebev) {
783                                         for (ring = 1; ring <= ns2; ring++) {
784                                                 for (k = ns - ns2; k < ns; k++) {
785                                                         if (ns % 2 == 0 && (k == ns2 || ring == ns2))
786                                                                 continue;
787                                                         create_mesh_bmvert(bm, vm, i, ring, k, bv->v);
788                                                 }
789                                         }
790                                 }
791                         }
792                 }
793         } while ((v = v->next) != vm->boundstart);
794
795         if (ns % 2 == 0) {
796                 /* Do special case center lines.
797                  * This loop makes verts for (i, ns2, k) for 1 <= k <= ns-1, k!=ns2
798                  * and for (i, r, ns2) for 1 <= r <= ns2-1,
799                  * whenever i is in a sequence of at least two beveled verts */
800                 v = vm->boundstart;
801                 do {
802                         i = v->index;
803                         if (v->ebev) {
804                                 vprev = v->prev;
805                                 vnext = v->next;
806                                 for (k = 1; k < ns2; k++) {
807                                         nv = mesh_vert(vm, i, k, ns2);
808                                         if (vprev->ebev)
809                                                 nvprev = mesh_vert(vm, vprev->index, ns2, ns - k);
810                                         if (vnext->ebev)
811                                                 nvnext = mesh_vert(vm, vnext->index, ns2, k);
812                                         if (vprev->ebev && vnext->ebev) {
813                                                 mid_v3_v3v3v3(co, nvprev->co, nv->co, nvnext->co);
814                                                 copy_v3_v3(nv->co, co);
815                                                 create_mesh_bmvert(bm, vm, i, k, ns2, bv->v);
816                                                 copy_mesh_vert(vm, vprev->index, ns2, ns - k, i, k, ns2);
817                                                 copy_mesh_vert(vm, vnext->index, ns2, k, i, k, ns2);
818
819                                         }
820                                         else if (vprev->ebev) {
821                                                 mid_v3_v3v3(co, nvprev->co, nv->co);
822                                                 copy_v3_v3(nv->co, co);
823                                                 create_mesh_bmvert(bm, vm, i, k, ns2, bv->v);
824                                                 copy_mesh_vert(vm, vprev->index, ns2, ns - k, i, k, ns2);
825
826                                                 create_mesh_bmvert(bm, vm, i, ns2, ns - k, bv->v);
827                                         }
828                                         else if (vnext->ebev) {
829                                                 mid_v3_v3v3(co, nv->co, nvnext->co);
830                                                 copy_v3_v3(nv->co, co);
831                                                 create_mesh_bmvert(bm, vm, i, k, ns2, bv->v);
832                                                 copy_mesh_vert(vm, vnext->index, ns2, k, i, k, ns2);
833
834                                                 create_mesh_bmvert(bm, vm, i, ns2, k, bv->v);
835                                         }
836                                 }
837                         }
838                 } while ((v = v->next) != vm->boundstart);
839
840                 /* center point need to be average of all centers of rings */
841                 /* TODO: this is wrong if not all verts have ebev: could have
842                  * several disconnected sections of mesh. */
843                 zero_v3(midco);
844                 nn = 0;
845                 v = vm->boundstart;
846                 do {
847                         i = v->index;
848                         if (v->ebev) {
849                                 nv = mesh_vert(vm, i, ns2, ns2);
850                                 add_v3_v3(midco, nv->co);
851                                 nn++;
852                         }
853                 } while ((v = v->next) != vm->boundstart);
854                 mul_v3_fl(midco, 1.0f / nn);
855                 bmv = BM_vert_create(bm, midco, NULL);
856                 v = vm->boundstart;
857                 do {
858                         i = v->index;
859                         if (v->ebev) {
860                                 nv = mesh_vert(vm, i, ns2, ns2);
861                                 copy_v3_v3(nv->co, midco);
862                                 nv->v = bmv;
863                         }
864                 } while ((v = v->next) != vm->boundstart);
865         }
866
867         /* Make the ring quads */
868         for (ring = 0; ring < ns2; ring++) {
869                 v = vm->boundstart;
870                 do {
871                         i = v->index;
872                         f = boundvert_rep_face(v);
873                         if (v->ebev && (v->prev->ebev || v->next->ebev)) {
874                                 for (k = 0; k < ns2 + (ns % 2); k++) {
875                                         bmv1 = mesh_vert(vm, i, ring, k)->v;
876                                         bmv2 = mesh_vert(vm, i, ring, k + 1)->v;
877                                         bmv3 = mesh_vert(vm, i, ring + 1, k + 1)->v;
878                                         bmv4 = mesh_vert(vm, i, ring + 1, k)->v;
879                                         BLI_assert(bmv1 && bmv2 && bmv3 && bmv4);
880                                         if (bmv3 == bmv4 || bmv1 == bmv4)
881                                                 bmv4 = NULL;
882                                         bev_create_quad_tri(bm, bmv1, bmv2, bmv3, bmv4, f);
883                                 }
884                         }
885                         else if (v->prev->ebev && v->prev->prev->ebev) {
886                                 /* finish off a sequence of beveled edges */
887                                 i = v->prev->index;
888                                 f = boundvert_rep_face(v->prev);
889                                 for (k = ns2 + (ns % 2); k < ns; k++) {
890                                         bmv1 = mesh_vert(vm, i, ring, k)->v;
891                                         bmv2 = mesh_vert(vm, i, ring, k + 1)->v;
892                                         bmv3 = mesh_vert(vm, i, ring + 1, k + 1)->v;
893                                         bmv4 = mesh_vert(vm, i, ring + 1, k)->v;
894                                         BLI_assert(bmv1 && bmv2 && bmv3 && bmv4);
895                                         if (bmv2 == bmv3) {
896                                                 bmv3 = bmv4;
897                                                 bmv4 = NULL;
898                                         }
899                                         bev_create_quad_tri(bm, bmv1, bmv2, bmv3, bmv4, f);
900                                 }
901                         }
902                 } while ((v = v->next) != vm->boundstart);
903         }
904
905         /* Make center ngon if odd number of segments and fully beveled */
906         if (ns % 2 == 1 && vm->count == bv->selcount) {
907                 BMVert **vv = NULL;
908                 BLI_array_declare(vv);
909
910                 v = vm->boundstart;
911                 do {
912                         i = v->index;
913                         BLI_assert(v->ebev);
914                         BLI_array_append(vv, mesh_vert(vm, i, ns2, ns2)->v);
915                 } while ((v = v->next) != vm->boundstart);
916                 f = boundvert_rep_face(vm->boundstart);
917                 bev_create_ngon(bm, vv, BLI_array_count(vv), f);
918
919                 BLI_array_free(vv);
920         }
921
922         /* Make 'rest-of-vmesh' polygon if not fully beveled */
923         if (vm->count > bv->selcount) {
924                 int j;
925                 BMVert **vv = NULL;
926                 BLI_array_declare(vv);
927
928                 v = vm->boundstart;
929                 f = boundvert_rep_face(v);
930                 j = 0;
931                 do {
932                         i = v->index;
933                         if (v->ebev) {
934                                 if (!v->prev->ebev) {
935                                         for (k = 0; k < ns2; k++) {
936                                                 bmv1 = mesh_vert(vm, i, ns2, k)->v;
937                                                 if (!bmv1)
938                                                         bmv1 = mesh_vert(vm, i, 0, k)->v;
939                                                 if (!(j > 0 && bmv1 == vv[j - 1])) {
940                                                         BLI_assert(bmv1 != NULL);
941                                                         BLI_array_append(vv, bmv1);
942                                                         j++;
943                                                 }
944                                         }
945                                 }
946                                 bmv1 = mesh_vert(vm, i, ns2, ns2)->v;
947                                 if (!bmv1)
948                                         bmv1 = mesh_vert(vm, i, 0, ns2)->v;
949                                 if (!(j > 0 && bmv1 == vv[j - 1])) {
950                                         BLI_assert(bmv1 != NULL);
951                                         BLI_array_append(vv, bmv1);
952                                         j++;
953                                 }
954                                 if (!v->next->ebev) {
955                                         for (k = ns - ns2; k < ns; k++) {
956                                                 bmv1 = mesh_vert(vm, i, ns2, k)->v;
957                                                 if (!bmv1)
958                                                         bmv1 = mesh_vert(vm, i, 0, k)->v;
959                                                 if (!(j > 0 && bmv1 == vv[j - 1])) {
960                                                         BLI_assert(bmv1 != NULL);
961                                                         BLI_array_append(vv, bmv1);
962                                                         j++;
963                                                 }
964                                         }
965                                 }
966                         }
967                         else {
968                                 BLI_assert(mesh_vert(vm, i, 0, 0)->v != NULL);
969                                 BLI_array_append(vv, mesh_vert(vm, i, 0, 0)->v);
970                                 j++;
971                         }
972                 } while ((v = v->next) != vm->boundstart);
973                 if (vv[0] == vv[j - 1])
974                         j--;
975                 bev_create_ngon(bm, vv, j, f);
976
977                 BLI_array_free(vv);
978         }
979 }
980
981 static BMFace *bevel_build_poly_ex(BMesh *bm, BevVert *bv)
982 {
983         BMFace *f;
984         int n, k;
985         VMesh *vm = bv->vmesh;
986         BoundVert *v;
987         BMVert **vv = NULL;
988         BLI_array_declare(vv);
989
990         v = vm->boundstart;
991         n = 0;
992         do {
993                 /* accumulate vertices for vertex ngon */
994                 BLI_array_append(vv, v->nv.v);
995                 n++;
996                 if (v->ebev && v->ebev->seg > 1) {
997                         for (k = 1; k < v->ebev->seg; k++) {
998                                 BLI_array_append(vv, mesh_vert(vm, v->index, 0, k)->v);
999                                 n++;
1000                         }
1001                 }
1002         } while ((v = v->next) != vm->boundstart);
1003         if (n > 2) {
1004                 f = bev_create_ngon(bm, vv, n, boundvert_rep_face(v));
1005         }
1006         else {
1007                 f = NULL;
1008         }
1009         BLI_array_free(vv);
1010         return f;
1011 }
1012
1013 static void bevel_build_poly(BMesh *bm, BevVert *bv)
1014 {
1015         bevel_build_poly_ex(bm, bv);
1016 }
1017
1018 static void bevel_build_trifan(BMesh *bm, BevVert *bv)
1019 {
1020         BMFace *f;
1021         BLI_assert(next_bev(bv, NULL)->seg == 1 || bv->selcount == 1);
1022
1023         f = bevel_build_poly_ex(bm, bv);
1024
1025         if (f) {
1026                 /* we have a polygon which we know starts at the previous vertex, make it into a fan */
1027                 BMLoop *l_fan = BM_FACE_FIRST_LOOP(f)->prev;
1028                 BMVert *v_fan = l_fan->v;
1029
1030                 while (f->len > 3) {
1031                         BMLoop *l_new;
1032                         BMFace *f_new;
1033                         BLI_assert(v_fan == l_fan->v);
1034                         f_new = BM_face_split(bm, f, l_fan->v, l_fan->next->next->v, &l_new, NULL, FALSE);
1035
1036                         if (f_new->len > f->len) {
1037                                 f = f_new;
1038                                 if      (l_new->v       == v_fan) { l_fan = l_new; }
1039                                 else if (l_new->next->v == v_fan) { l_fan = l_new->next; }
1040                                 else if (l_new->prev->v == v_fan) { l_fan = l_new->prev; }
1041                                 else { BLI_assert(0); }
1042                         }
1043                         else {
1044                                 if      (l_fan->v       == v_fan) { l_fan = l_fan; }
1045                                 else if (l_fan->next->v == v_fan) { l_fan = l_fan->next; }
1046                                 else if (l_fan->prev->v == v_fan) { l_fan = l_fan->prev; }
1047                                 else { BLI_assert(0); }
1048                         }
1049                 }
1050         }
1051 }
1052
1053 static void bevel_build_quadstrip(BMesh *bm, BevVert *bv)
1054 {
1055         BMFace *f;
1056         BLI_assert(bv->selcount == 2);
1057
1058         f = bevel_build_poly_ex(bm, bv);
1059
1060         if (f) {
1061                 /* we have a polygon which we know starts at this vertex, make it into strips */
1062                 BMVert *v_first = bv->vmesh->boundstart->efirst->next->next->leftv->nv.v;  /* magic? */
1063                 //BMLoop *l_start = BM_FACE_FIRST_LOOP(f);
1064                 BMLoop *l_start = BM_face_vert_share_loop(f, v_first);
1065                 BMLoop *l_a = l_start->prev, *l_a_step;
1066                 BMLoop *l_b = l_start->next, *l_b_step;
1067
1068                 while (f->len > 4) {
1069                         // BMLoop *l_new;
1070                         BMFace *f_new;
1071                         BLI_assert(l_a->f == f);
1072                         BLI_assert(l_b->f == f);
1073
1074                         l_a_step = l_a->prev;
1075                         l_b_step = l_b->next;
1076
1077                         f_new = BM_face_split(bm, f, l_a->v, l_b->v, NULL, NULL, FALSE);
1078
1079                         if (f_new->len > f->len) {
1080                                 f = f_new;
1081                         }
1082
1083                         l_a = l_a_step;
1084                         l_b = l_b_step;
1085                 }
1086         }
1087 }
1088
1089 /* Given that the boundary is built, now make the actual BMVerts
1090  * for the boundary and the interior of the vertex mesh. */
1091 static void build_vmesh(BMesh *bm, BevVert *bv)
1092 {
1093         VMesh *vm = bv->vmesh;
1094         BoundVert *v, *weld1, *weld2;
1095         int n, ns, ns2, i, k, weld;
1096         float *va, *vb, co[3], midco[3];
1097
1098         n = vm->count;
1099         ns = vm->seg;
1100         ns2 = ns / 2;
1101
1102         vm->mesh = (NewVert *)MEM_callocN(n * (ns2 + 1) * (ns + 1) * sizeof(NewVert), "NewVert");
1103
1104         /* special case: two beveled ends welded together */
1105         weld = (bv->selcount == 2) && (vm->count == 2);
1106         weld1 = weld2 = NULL;   /* will hold two BoundVerts involved in weld */
1107
1108         /* make (i, 0, 0) mesh verts for all i */
1109         v = vm->boundstart;
1110         do {
1111                 i = v->index;
1112                 copy_v3_v3(mesh_vert(vm, i, 0, 0)->co, v->nv.co);
1113                 create_mesh_bmvert(bm, vm, i, 0, 0, bv->v);
1114                 v->nv.v = mesh_vert(vm, i, 0, 0)->v;
1115                 if (weld && v->ebev) {
1116                         if (!weld1)
1117                                 weld1 = v;
1118                         else
1119                                 weld2 = v;
1120                 }
1121         } while ((v = v->next) != vm->boundstart);
1122
1123         /* copy other ends to (i, 0, ns) for all i, and fill in profiles for beveled edges */
1124         v = vm->boundstart;
1125         do {
1126                 i = v->index;
1127                 copy_mesh_vert(vm, i, 0, ns, v->next->index, 0, 0);
1128                 if (v->ebev) {
1129                         va = mesh_vert(vm, i, 0, 0)->co;
1130                         vb = mesh_vert(vm, i, 0, ns)->co;
1131                         project_to_edge(v->ebev->e, va, vb, midco);
1132                         for (k = 1; k < ns; k++) {
1133                                 get_point_on_round_edge(v->ebev, k, va, midco, vb, co);
1134                                 copy_v3_v3(mesh_vert(vm, i, 0, k)->co, co);
1135                                 if (!weld)
1136                                         create_mesh_bmvert(bm, vm, i, 0, k, bv->v);
1137                         }
1138                 }
1139         } while ((v = v->next) != vm->boundstart);
1140
1141         if (weld) {
1142                 vm->mesh_kind = M_NONE;
1143                 for (k = 1; k < ns; k++) {
1144                         va = mesh_vert(vm, weld1->index, 0, k)->co;
1145                         vb = mesh_vert(vm, weld2->index, 0, ns - k)->co;
1146                         mid_v3_v3v3(co, va, vb);
1147                         copy_v3_v3(mesh_vert(vm, weld1->index, 0, k)->co, co);
1148                         create_mesh_bmvert(bm, vm, weld1->index, 0, k, bv->v);
1149                 }
1150                 for (k = 1; k < ns; k++)
1151                         copy_mesh_vert(vm, weld2->index, 0, ns - k, weld1->index, 0, k);
1152         }
1153
1154         if (vm->mesh_kind == M_ADJ)
1155                 bevel_build_rings(bm, bv);
1156         else if (vm->mesh_kind == M_POLY)
1157                 bevel_build_poly(bm, bv);
1158         else if (vm->mesh_kind == M_TRI_FAN)
1159                 bevel_build_trifan(bm, bv);
1160         else if (vm->mesh_kind == M_QUAD_STRIP)
1161                 bevel_build_quadstrip(bm, bv);
1162 }
1163
1164 /*
1165  * Construction around the vertex
1166  */
1167 static void bevel_vert_construct(BMesh *bm, BevelParams *bp, BMOperator *op, BMVert *v)
1168 {
1169
1170         BMOIter siter;
1171         BMEdge *bme;
1172         BevVert *bv;
1173         BMEdge *bme2, *unflagged_bme;
1174         BMFace *f;
1175         BMIter iter, iter2;
1176         EdgeHalf *e;
1177         int i, ntot, found_shared_face, ccw_test_sum;
1178         int nsel = 0;
1179
1180         /* Gather input selected edges.
1181          * Only bevel selected edges that have exactly two incident faces.
1182          *
1183          * TODO, optimization - we could tag edges in 'geom'
1184          * and then just iterate edges-of-vert, checking tags.
1185          */
1186         BMO_ITER (bme, &siter, bm, op, "geom", BM_EDGE) {
1187                 if (BM_vert_in_edge(bme, v)) {
1188                         if (BM_edge_is_manifold(bme)) {
1189                                 BMO_elem_flag_enable(bm, bme, EDGE_SELECTED);
1190                                 nsel++;
1191                         }
1192                 }
1193         }
1194
1195         if (nsel == 0)
1196                 return;
1197
1198         ntot = BM_vert_edge_count(v);
1199         bv = (BevVert *)MEM_callocN(sizeof(BevVert), "BevVert");
1200         bv->v = v;
1201         bv->edgecount = ntot;
1202         bv->selcount = nsel;
1203         bv->edges = (EdgeHalf *)MEM_callocN(ntot * sizeof(EdgeHalf), "EdgeHalf");
1204         bv->vmesh = (VMesh *)MEM_callocN(sizeof(VMesh), "VMesh");
1205         bv->vmesh->seg = bp->seg;
1206         BLI_addtail(&bp->vertList, bv);
1207
1208         /* add edges to bv->edges in order that keeps adjacent edges sharing
1209          * a face, if possible */
1210         i = 0;
1211         bme = v->e;
1212         BMO_elem_flag_enable(bm, bme, BEVEL_FLAG);
1213         e = &bv->edges[0];
1214         e->e = bme;
1215         for (i = 0; i < ntot; i++) {
1216                 if (i > 0) {
1217                         /* find an unflagged edge bme2 that shares a face f with previous bme */
1218                         found_shared_face = 0;
1219                         unflagged_bme = NULL;
1220                         BM_ITER_ELEM (bme2, &iter, v, BM_EDGES_OF_VERT) {
1221                                 if (BMO_elem_flag_test(bm, bme2, BEVEL_FLAG))
1222                                         continue;
1223                                 if (!unflagged_bme)
1224                                         unflagged_bme = bme2;
1225                                 BM_ITER_ELEM (f, &iter2, bme2, BM_FACES_OF_EDGE) {
1226                                         if (BM_face_edge_share_loop(f, bme)) {
1227                                                 found_shared_face = 1;
1228                                                 break;
1229                                         }
1230                                 }
1231                                 if (found_shared_face)
1232                                         break;
1233                         }
1234                         e = &bv->edges[i];
1235                         if (found_shared_face) {
1236                                 e->e = bme2;
1237                                 e->fprev = f;
1238                                 bv->edges[i - 1].fnext = f;
1239                         }
1240                         else {
1241                                 e->e = unflagged_bme;
1242                         }
1243                 }
1244                 bme = e->e;
1245                 BMO_elem_flag_enable(bm, bme, BEVEL_FLAG);
1246                 if (BMO_elem_flag_test(bm, bme, EDGE_SELECTED)) {
1247                         e->isbev = 1;
1248                         e->seg = bp->seg;
1249                 }
1250                 else {
1251                         e->isbev = 0;
1252                         e->seg = 0;
1253                 }
1254                 e->isrev = (bme->v2 == v);
1255                 e->offset = e->isbev ? bp->offset : 0.0f;
1256         }
1257         /* find wrap-around shared face */
1258         BM_ITER_ELEM (f, &iter2, bme, BM_FACES_OF_EDGE) {
1259                 if (BM_face_edge_share_loop(f, bv->edges[0].e)) {
1260                         if (bv->edges[0].fnext == f)
1261                                 continue;   /* if two shared faces, want the other one now */
1262                         bv->edges[ntot - 1].fnext = f;
1263                         bv->edges[0].fprev = f;
1264                         break;
1265                 }
1266         }
1267
1268         /* remove BEVEL_FLAG now that we are finished with it*/
1269         for (i = 0; i < ntot; i++)
1270                 BMO_elem_flag_disable(bm, bv->edges[i].e, BEVEL_FLAG);
1271
1272         /* if edge array doesn't go CCW around vertex from average normal side,
1273          * reverse the array, being careful to reverse face pointers too */
1274         if (ntot > 1) {
1275                 ccw_test_sum = 0;
1276                 for (i = 0; i < ntot; i++)
1277                         ccw_test_sum += bev_ccw_test(bv->edges[i].e, bv->edges[(i + 1) % ntot].e,
1278                                                      bv->edges[i].fnext);
1279                 if (ccw_test_sum < 0) {
1280                         for (i = 0; i <= (ntot / 2) - 1; i++) {
1281                                 SWAP(EdgeHalf, bv->edges[i], bv->edges[ntot - i - 1]);
1282                                 SWAP(BMFace *, bv->edges[i].fprev, bv->edges[i].fnext);
1283                                 SWAP(BMFace *, bv->edges[ntot - i - 1].fprev, bv->edges[ntot - i - 1].fnext);
1284                         }
1285                         if (ntot % 2 == 1) {
1286                                 i = ntot / 2;
1287                                 SWAP(BMFace *, bv->edges[i].fprev,  bv->edges[i].fnext);
1288                         }
1289                 }
1290         }
1291
1292         for (i = 0; i < ntot; i++) {
1293                 e = &bv->edges[i];
1294                 e->next = &bv->edges[(i + 1) % ntot];
1295                 e->prev = &bv->edges[(i + ntot - 1) % ntot];
1296         }
1297
1298         build_boundary(bv);
1299         build_vmesh(bm, bv);
1300 }
1301
1302 /* Face f has at least one beveled vertex.  Rebuild f */
1303 static void rebuild_polygon(BMesh *bm, BevelParams *bp, BMFace *f)
1304 {
1305         BMIter liter;
1306         BMLoop *l, *lprev;
1307         BevVert *bv;
1308         BoundVert *v, *vstart, *vend;
1309         EdgeHalf *e, *eprev;
1310         VMesh *vm;
1311         int i, k;
1312         BMVert *bmv;
1313         BMVert **vv = NULL;
1314         BLI_array_declare(vv);
1315
1316         BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
1317                 bv = find_bevvert(bp, l->v);
1318                 if (bv) {
1319                         lprev = l->prev;
1320                         e = find_edge_half(bv, l->e);
1321                         eprev = find_edge_half(bv, lprev->e);
1322                         BLI_assert(e != NULL && eprev != NULL);
1323                         vstart = eprev->leftv;
1324                         if (e->isbev)
1325                                 vend = e->rightv;
1326                         else
1327                                 vend = e->leftv;
1328                         v = vstart;
1329                         vm = bv->vmesh;
1330                         BLI_array_append(vv, v->nv.v);
1331                         while (v != vend) {
1332                                 if (vm->mesh_kind == M_NONE && v->ebev && v->ebev->seg > 1 && v->ebev != e && v->ebev != eprev) {
1333                                         /* case of 3rd face opposite a beveled edge, with no vmesh */
1334                                         i = v->index;
1335                                         e = v->ebev;
1336                                         for (k = 1; k < e->seg; k++) {
1337                                                 bmv = mesh_vert(vm, i, 0, k)->v;
1338                                                 BLI_array_append(vv, bmv);
1339                                         }
1340                                 }
1341                                 v = v->prev;
1342                                 BLI_array_append(vv, v->nv.v);
1343                         }
1344                 }
1345                 else {
1346                         BLI_array_append(vv, l->v);
1347                 }
1348         }
1349         bev_create_ngon(bm, vv, BLI_array_count(vv), f);
1350         BLI_array_free(vv);
1351 }
1352
1353 /* All polygons touching v need rebuilding because beveling v has made new vertices */
1354 static void bevel_rebuild_existing_polygons(BMesh *bm, BevelParams *bp, BMVert *v)
1355 {
1356         void    *faces_stack[BM_DEFAULT_ITER_STACK_SIZE];
1357         int      faces_len, f_index;
1358         BMFace **faces = BM_iter_as_arrayN(bm, BM_FACES_OF_VERT, v, &faces_len,
1359                                            faces_stack, BM_DEFAULT_ITER_STACK_SIZE);
1360
1361         if (LIKELY(faces != NULL)) {
1362                 for (f_index = 0; f_index < faces_len; f_index++) {
1363                         BMFace *f = faces[f_index];
1364                         rebuild_polygon(bm, bp, f);
1365                         BM_face_kill(bm, f);
1366                 }
1367
1368                 if (faces != (BMFace **)faces_stack) {
1369                         MEM_freeN(faces);
1370                 }
1371         }
1372 }
1373
1374
1375
1376 /*
1377  * Build the polygons along the selected Edge
1378  */
1379 static void bevel_build_edge_polygons(BMesh *bm, BevelParams *bp, BMEdge *bme)
1380 {
1381         BevVert *bv1, *bv2;
1382         BMVert *bmv1, *bmv2, *bmv3, *bmv4, *bmv1i, *bmv2i, *bmv3i, *bmv4i;
1383         VMesh *vm1, *vm2;
1384         EdgeHalf *e1, *e2;
1385         BMFace *f1, *f2, *f;
1386         int k, nseg, i1, i2;
1387
1388         if (!BM_edge_is_manifold(bme))
1389                 return;
1390
1391         bv1 = find_bevvert(bp, bme->v1);
1392         bv2 = find_bevvert(bp, bme->v2);
1393
1394         BLI_assert(bv1 && bv2);
1395
1396         e1 = find_edge_half(bv1, bme);
1397         e2 = find_edge_half(bv2, bme);
1398
1399         BLI_assert(e1 && e2);
1400
1401         /*   v4             v3
1402          *    \            /
1403          *     e->v1 - e->v2
1404          *    /            \
1405          *   v1             v2
1406          */
1407         nseg = e1->seg;
1408         BLI_assert(nseg > 0 && nseg == e2->seg);
1409
1410         bmv1 = e1->leftv->nv.v;
1411         bmv4 = e1->rightv->nv.v;
1412         bmv2 = e2->rightv->nv.v;
1413         bmv3 = e2->leftv->nv.v;
1414
1415         BLI_assert(bmv1 && bmv2 && bmv3 && bmv4);
1416
1417         f1 = boundvert_rep_face(e1->leftv);
1418         f2 = boundvert_rep_face(e1->rightv);
1419
1420         if (nseg == 1) {
1421                 bev_create_quad_tri(bm, bmv1, bmv2, bmv3, bmv4, f1);
1422         }
1423         else {
1424                 i1 = e1->leftv->index;
1425                 i2 = e2->leftv->index;
1426                 vm1 = bv1->vmesh;
1427                 vm2 = bv2->vmesh;
1428                 bmv1i = bmv1;
1429                 bmv2i = bmv2;
1430                 for (k = 1; k <= nseg; k++) {
1431                         bmv4i = mesh_vert(vm1, i1, 0, k)->v;
1432                         bmv3i = mesh_vert(vm2, i2, 0, nseg - k)->v;
1433                         f = (k <= nseg / 2 + (nseg % 2)) ? f1 : f2;
1434                         bev_create_quad_tri(bm, bmv1i, bmv2i, bmv3i, bmv4i, f);
1435                         bmv1i = bmv4i;
1436                         bmv2i = bmv3i;
1437                 }
1438         }
1439 }
1440
1441
1442 static void free_bevel_params(BevelParams *bp)
1443 {
1444         BevVert *bv;
1445         VMesh *vm;
1446         BoundVert *v, *vnext;
1447
1448         for (bv = bp->vertList.first; bv; bv = bv->next) {
1449                 MEM_freeN(bv->edges);
1450                 vm = bv->vmesh;
1451                 v = vm->boundstart;
1452                 if (v) {
1453                         do {
1454                                 vnext = v->next;
1455                                 MEM_freeN(v);
1456                         } while ((v = vnext) != vm->boundstart);
1457                 }
1458                 if (vm->mesh)
1459                         MEM_freeN(vm->mesh);
1460                 MEM_freeN(vm);
1461         }
1462         BLI_freelistN(&bp->vertList);
1463 }
1464
1465 void bmo_bevel_exec(BMesh *bm, BMOperator *op)
1466 {
1467         BMOIter siter;
1468         BMVert *v;
1469         BMEdge *e;
1470         BevelParams bp = {{NULL}};
1471
1472         bp.offset = BMO_slot_float_get(op, "offset");
1473         bp.op = op;
1474         bp.seg = BMO_slot_int_get(op, "segments");
1475
1476         if (bp.offset > 0) {
1477                 /* The analysis of the input vertices and execution additional constructions */
1478                 BMO_ITER (v, &siter, bm, op, "geom", BM_VERT) {
1479                         bevel_vert_construct(bm, &bp, op, v);
1480                 }
1481                 /* Build polygons for edges */
1482                 BMO_ITER (e, &siter, bm, op, "geom", BM_EDGE) {
1483                         bevel_build_edge_polygons(bm, &bp, e);
1484                 }
1485
1486                 BMO_ITER (v, &siter, bm, op, "geom", BM_VERT) {
1487                         bevel_rebuild_existing_polygons(bm, &bp, v);
1488                 }
1489
1490                 BMO_ITER (v, &siter, bm, op, "geom", BM_VERT) {
1491                         if (find_bevvert(&bp, v))
1492                                 BM_vert_kill(bm, v);
1493                 }
1494                 free_bevel_params(&bp);
1495         }
1496 }