code cleanup: spelling,
[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 NEW_BEVEL 1
41
42 #ifdef NEW_BEVEL
43 #define BEVEL_FLAG      1
44 #define EDGE_SELECTED   2
45
46 #define BEVEL_EPSILON  1e-6
47
48 /* Constructed vertex, sometimes later instantiated as BMVert */
49 typedef struct NewVert {
50         float co[3];
51         BMVert *v;
52 } NewVert;
53
54 struct BoundVert;
55
56 /* Data for one end of an edge involved in a bevel */
57 typedef struct EdgeHalf {
58         struct EdgeHalf *next, *prev;   /* in CCW order */
59         BMEdge *e;                  /* original mesh edge */
60         int isbev;                  /* is this edge beveled? */
61         int isrev;                  /* is e->v2 the vertex at this end? */
62         int seg;                    /* how many segments for the bevel */
63         float offset;               /* offset for this 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 } EdgeHalf;
69
70 /* An element in a cyclic boundary of a Vertex Mesh (VMesh) */
71 typedef struct BoundVert {
72         struct BoundVert *next, *prev;  /* in CCW order */
73         int index;          /* used for vmesh indexing */
74         NewVert nv;
75         EdgeHalf *efirst;   /* first of edges attached here: in CCW order */
76         EdgeHalf *elast;
77         EdgeHalf *ebev;     /* beveled edge whose left side is attached here, if any */
78 } BoundVert;
79
80 /* Mesh structure replacing a vertex */
81 typedef struct VMesh {
82         enum {
83                 M_NONE,         /* no polygon mesh needed */
84                 M_POLY,         /* a simple polygon */
85                 M_ADJ,          /* "adjacent edges" mesh pattern */
86                 M_CROSS,        /* "cross edges" mesh pattern */
87         } mesh_kind;
88         int count;          /* number of vertices in the boundary */
89         int seg;            /* common # of segments for segmented edges */
90         BoundVert *boundstart;      /* start of boundary double-linked list */
91         NewVert *mesh;          /* allocated array - size and structure depends on kind */
92 } VMesh;
93
94 /* Data for a vertex involved in a bevel */
95 typedef struct BevVert {
96         struct BevVert *next, *prev;
97         BMVert *v;          /* original mesh vertex */
98         int edgecount;          /* total number of edges around the vertex */
99         int selcount;           /* number of selected edges around the vertex */
100         EdgeHalf *edges;        /* array of size edgecount; CCW order from vertex normal side */
101         VMesh *vmesh;           /* mesh structure for replacing vertex */
102 } BevVert;
103
104 /*
105  * Bevel parameters and state
106  */
107 typedef struct BevelParams {
108         ListBase vertList;      /* list of BevVert for each vertex involved in bevel */
109         float offset;           /* blender units to offset each side of a beveled edge */
110         int seg;                /* number of segments in beveled edge profile */
111
112         BMOperator *op;
113 } BevelParams;
114
115 /* Make a new BoundVert of the given kind, insert it at the end of the circular linked
116  * list with entry point bv->boundstart, and return it. */
117 static BoundVert *add_new_bound_vert(VMesh *vm, float co[3])
118 {
119         BoundVert *ans = (BoundVert *) MEM_callocN(sizeof(BoundVert), "BoundVert");
120         copy_v3_v3(ans->nv.co, co);
121         if (!vm->boundstart) {
122                 ans->index = 0;
123                 vm->boundstart = ans;
124                 ans->next = ans->prev = ans;
125         }
126         else {
127                 BoundVert *tail = vm->boundstart->prev;
128                 ans->index = tail->index + 1;
129                 ans->prev = tail;
130                 ans->next = vm->boundstart;
131                 tail->next = ans;
132                 vm->boundstart->prev = ans;
133         }
134         vm->count++;
135         return ans;
136 }
137
138 /* Mesh verts are indexed (i, j, k) where
139  * i = boundvert index (0 <= i < nv)
140  * j = ring index (0 <= j <= ns2)
141  * k = segment index (0 <= k <= ns)
142  * Not all of these are used, and some will share BMVerts */
143 static NewVert *mesh_vert(VMesh *vm, int i, int j, int k)
144 {
145         int nj = (vm->seg / 2) + 1;
146         int nk = vm->seg + 1;
147
148         return &vm->mesh[i * nk * nj  + j * nk + k];
149 }
150
151 static void create_mesh_bmvert(BMesh *bm, VMesh *vm, int i, int j, int k, BMVert *eg)
152 {
153         NewVert *nv = mesh_vert(vm, i, j, k);
154         nv->v = BM_vert_create(bm, nv->co, eg);
155 }
156
157 static void copy_mesh_vert(VMesh *vm, int ito, int jto, int kto,
158                            int ifrom, int jfrom, int kfrom)
159 {
160         NewVert *nvto, *nvfrom;
161
162         nvto = mesh_vert(vm, ito, jto, kto);
163         nvfrom = mesh_vert(vm, ifrom, jfrom, kfrom);
164         nvto->v = nvfrom->v;
165         copy_v3_v3(nvto->co, nvfrom->co);
166 }
167
168 /* find the EdgeHalf in bv's array that has edge bme */
169 static EdgeHalf *find_edge_half(BevVert *bv, BMEdge *bme)
170 {
171         int i;
172
173         for (i = 0; i < bv->edgecount; i++) {
174                 if (bv->edges[i].e == bme)
175                         return &bv->edges[i];
176         }
177         return NULL;
178 }
179
180 /* Return the next EdgeHalf after from_e that is beveled.
181  * If from_e is NULL, find the first beveled edge. */
182 static EdgeHalf *next_bev(BevVert *bv, EdgeHalf *from_e)
183 {
184         EdgeHalf *e;
185
186         if (from_e == NULL)
187                 from_e = &bv->edges[bv->edgecount - 1];
188         e = from_e;
189         do {
190                 if (e->isbev)
191                         return e;
192                 e = e->next;
193         } while (e != from_e);
194         return NULL;
195 }
196
197 /* find the BevVert corresponding to BMVert bmv */
198 static BevVert *find_bevvert(BevelParams *bp, BMVert *bmv)
199 {
200         BevVert *bv;
201
202         for (bv = bp->vertList.first; bv; bv = bv->next) {
203                 if (bv->v == bmv)
204                         return bv;
205         }
206         return NULL;
207 }
208
209 /* Return a good respresentative face (for materials, etc.) for faces
210  * created around/near BoundVert v */
211 static BMFace *boundvert_rep_face(BoundVert *v)
212 {
213         BMFace *fans = NULL;
214         BMFace *firstf = NULL;
215         BMEdge *e1, *e2;
216         BMFace *f1, *f2;
217         BMIter iter1, iter2;
218
219         BLI_assert(v->efirst != NULL && v->elast != NULL);
220         e1 = v->efirst->e;
221         e2 = v->elast->e;
222         BM_ITER_ELEM (f1, &iter1, e1, BM_FACES_OF_EDGE) {
223                 if (!firstf)
224                         firstf = f1;
225                 BM_ITER_ELEM (f2, &iter2, e2, BM_FACES_OF_EDGE) {
226                         if (f1 == f2) {
227                                 fans = f1;
228                                 break;
229                         }
230                 }
231         }
232         if (!fans)
233                 fans = firstf;
234
235         return fans;
236 }
237
238 /* Make ngon from verts alone.
239  * Make sure to properly copy face attributes and do custom data interpolation from
240  * example face, facerep. */
241 static BMFace *bev_create_ngon(BMesh *bm, BMVert **vert_arr, int totv, BMFace *facerep)
242 {
243         BMIter iter;
244         BMLoop *l;
245         BMFace *f;
246
247         if (totv == 3) {
248                 f = BM_face_create_quad_tri(bm,
249                                             vert_arr[0], vert_arr[1], vert_arr[2], NULL, facerep, 0);
250         }
251         else if (totv == 4) {
252                 f = BM_face_create_quad_tri(bm,
253                                             vert_arr[0], vert_arr[1], vert_arr[2], vert_arr[3], facerep, 0);
254         }
255         else {
256                 int i;
257                 BMEdge *e;
258                 BMEdge **ee = NULL;
259                 BLI_array_staticdeclare(ee, 30);
260
261                 for (i = 0; i < totv; i++) {
262                         e = BM_edge_create(bm, vert_arr[i], vert_arr[(i + 1) % totv], NULL, TRUE);
263                         BLI_array_append(ee, e);
264                 }
265                 f = BM_face_create_ngon(bm, vert_arr[0], vert_arr[1], ee, totv, FALSE);
266                 BLI_array_free(ee);
267         }
268         if (facerep && f) {
269                 int has_mdisps = CustomData_has_layer(&bm->ldata, CD_MDISPS);
270                 BM_elem_attrs_copy(bm, bm, facerep, f);
271                 BM_ITER_ELEM (l, &iter, f, BM_LOOPS_OF_FACE) {
272                         BM_loop_interp_from_face(bm, l, facerep, TRUE, TRUE);
273                         if (has_mdisps)
274                                 BM_loop_interp_multires(bm, l, facerep);
275                 }
276         }
277         return f;
278 }
279
280 static BMFace *bev_create_quad_tri(BMesh *bm, BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4,
281                                    BMFace *facerep)
282 {
283         BMVert *varr[4];
284
285         varr[0] = v1;
286         varr[1] = v2;
287         varr[2] = v3;
288         varr[3] = v4;
289         return bev_create_ngon(bm, varr, v4 ? 4 : 3, facerep);
290 }
291
292 /*
293  * Calculate the meeting point between the offset edges for e1 and e2, putting answer in meetco.
294  * e1 and e2 share vertex v and face f (may be NULL) and viewed from the normal side of
295  * the bevel vertex,  e1 precedes e2 in CCW order.
296  * If on_right is true, offset edge is on right of both edges, where e1 enters v and
297  * e2 leave it. If on_right is false, then the offset edge is on the left.
298  * When offsets are equal, the new point is on the edge bisector, with length offset/sin(angle/2),
299  * but if the offsets are not equal (allowing for this, as bevel modifier has edge weights that may
300  * lead to different offsets) then meeting point can be found be intersecting offset lines.
301  */
302 static void offset_meet(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, BMFace *f,
303                         int on_right, float meetco[3])
304 {
305         float dir1[3], dir2[3], norm_v[3], norm_perp1[3], norm_perp2[3],
306               off1a[3], off1b[3], off2a[3], off2b[3], isect2[3];
307
308         /* get direction vectors for two offset lines */
309         sub_v3_v3v3(dir1, v->co, BM_edge_other_vert(e1->e, v)->co);
310         sub_v3_v3v3(dir2, BM_edge_other_vert(e2->e, v)->co, v->co);
311
312         /* get normal to plane where meet point should be */
313         cross_v3_v3v3(norm_v, dir2, dir1);
314         normalize_v3(norm_v);
315         if (!on_right)
316                 negate_v3(norm_v);
317         if (is_zero_v3(norm_v)) {
318                 /* special case: e1 and e2 are parallel; put offset point perp to both, from v.
319                  * need to find a suitable plane.
320                  * if offsets are different, we're out of luck: just use e1->offset */
321                 if (f)
322                         copy_v3_v3(norm_v, f->no);
323                 else
324                         copy_v3_v3(norm_v, v->no);
325                 cross_v3_v3v3(norm_perp1, dir1, norm_v);
326                 normalize_v3(norm_perp1);
327                 copy_v3_v3(off1a, v->co);
328                 madd_v3_v3fl(off1a, norm_perp1, e1->offset);
329                 copy_v3_v3(meetco, off1a);
330         }
331         else {
332                 /* get vectors perp to each edge, perp to norm_v, and pointing into face */
333                 if (f) {
334                         copy_v3_v3(norm_v, f->no);
335                         normalize_v3(norm_v);
336                 }
337                 cross_v3_v3v3(norm_perp1, dir1, norm_v);
338                 cross_v3_v3v3(norm_perp2, dir2, norm_v);
339                 normalize_v3(norm_perp1);
340                 normalize_v3(norm_perp2);
341
342                 /* get points that are offset distances from each line, then another point on each line */
343                 copy_v3_v3(off1a, v->co);
344                 madd_v3_v3fl(off1a, norm_perp1, e1->offset);
345                 add_v3_v3v3(off1b, off1a, dir1);
346                 copy_v3_v3(off2a, v->co);
347                 madd_v3_v3fl(off2a, norm_perp2, e2->offset);
348                 add_v3_v3v3(off2b, off2a, dir2);
349
350                 /* intersect the lines; by construction they should be on the same plane and not parallel */
351                 if (!isect_line_line_v3(off1a, off1b, off2a, off2b, meetco, isect2)) {
352                         BLI_assert(!"offset_meet failure");
353                         copy_v3_v3(meetco, off1a);  /* just to do something */
354                 }
355         }
356 }
357
358 /* Like offset_meet, but here f1 and f2 must not be NULL and give the
359  * planes in which to run the offset lines.  They may not meet exactly,
360  * but the line intersection routine will find the closest approach point. */
361 static void offset_in_two_planes(EdgeHalf *e1, EdgeHalf *e2, BMVert *v,
362                                  BMFace *f1, BMFace *f2, float meetco[3])
363 {
364         float dir1[3], dir2[3], norm_perp1[3], norm_perp2[3],
365               off1a[3], off1b[3], off2a[3], off2b[3], isect2[3];
366
367         BLI_assert(f1 != NULL && f2 != NULL);
368
369         /* get direction vectors for two offset lines */
370         sub_v3_v3v3(dir1, v->co, BM_edge_other_vert(e1->e, v)->co);
371         sub_v3_v3v3(dir2, BM_edge_other_vert(e2->e, v)->co, v->co);
372
373         /* get directions into offset planes */
374         cross_v3_v3v3(norm_perp1, dir1, f1->no);
375         normalize_v3(norm_perp1);
376         cross_v3_v3v3(norm_perp2, dir2, f2->no);
377         normalize_v3(norm_perp2);
378
379         /* get points that are offset distances from each line, then another point on each line */
380         copy_v3_v3(off1a, v->co);
381         madd_v3_v3fl(off1a, norm_perp1, e1->offset);
382         add_v3_v3v3(off1b, off1a, dir1);
383         copy_v3_v3(off2a, v->co);
384         madd_v3_v3fl(off2a, norm_perp2, e2->offset);
385         add_v3_v3v3(off2b, off2a, dir2);
386
387         if (!isect_line_line_v3(off1a, off1b, off2a, off2b, meetco, isect2)) {
388                 /* lines are parallel; off1a is a good meet point */
389                 copy_v3_v3(meetco, off1a);
390         }
391 }
392
393 /* Offset by e->offset in plane with normal plane_no, on left if left==TRUE,
394  * else on right.  If no is NULL, choose an arbitrary plane different
395  * from eh's direction. */
396 static void offset_in_plane(EdgeHalf *e, float plane_no[3], int left, float r[3])
397 {
398         float dir[3], no[3];
399         BMVert *v;
400
401         v = e->isrev ? e->e->v1 : e->e->v2;
402
403         sub_v3_v3v3(dir, BM_edge_other_vert(e->e, v)->co, v->co);
404         normalize_v3(dir);
405         if (plane_no) {
406                 copy_v3_v3(no, plane_no);
407         }
408         else {
409                 zero_v3(no);
410                 if (fabs(dir[0]) < fabs(dir[1]))
411                         no[0] = 1.0f;
412                 else
413                         no[1] = 1.0f;
414         }
415         if (left)
416                 cross_v3_v3v3(r, no, dir);
417         else
418                 cross_v3_v3v3(r, dir, no);
419         normalize_v3(r);
420         mul_v3_fl(r, e->offset);
421 }
422
423 /* Calculate coordinates of a point a distance d from v on e->e and return it in slideco */
424 static void slide_dist(EdgeHalf *e, BMVert *v, float d, float slideco[3])
425 {
426         float dir[3], len;
427
428         sub_v3_v3v3(dir, v->co, BM_edge_other_vert(e->e, v)->co);
429         len = len_v3(dir);
430         normalize_v3(dir);
431         if (d > len)
432                 d = len - (float)(50 * BEVEL_EPSILON);
433         copy_v3_v3(slideco, v->co);
434         madd_v3_v3fl(slideco, dir, -d);
435 }
436
437 /* Calculate the point on e where line (co_a, co_b) comes closest to and return it in projco */
438 static void project_to_edge(BMEdge *e, float co_a[3], float co_b[3], float projco[3])
439 {
440         float otherco[3];
441
442         if (!isect_line_line_v3(e->v1->co, e->v2->co, co_a, co_b,
443                                 projco, otherco)) {
444                 BLI_assert(!"project meet failure");
445                 copy_v3_v3(projco, e->v1->co);
446         }
447 }
448
449
450 /* return 1 if a and b are in CCW order on the normal side of f,
451  * and -1 if they are reversed, and 0 if there is no shared face f */
452 static int bev_ccw_test(BMEdge *a, BMEdge *b, BMFace *f)
453 {
454         BMLoop *la, *lb;
455
456         if (!f)
457                 return 0;
458         la = BM_face_edge_share_loop(f, a);
459         lb = BM_face_edge_share_loop(f, b);
460         if (!la || !lb)
461                 return 0;
462         return lb->next == la ? 1 : -1;
463 }
464
465 /*
466  * calculation of points on the round profile
467  * r - result, coordinate of point on round profile
468  * method:
469  * Inscribe a circle in angle va - v -vb
470  * such that it touches the arms at offset from v.
471  * Rotate the center-va segment by (i/n) of the
472  * angle va - center -vb, and put the endpoint
473  * of that segment in r.
474  */
475 static void get_point_on_round_profile(float r[3], float offset, int i, int count,
476                                        float va[3], float v[3], float vb[3])
477 {
478         float vva[3], vvb[3], angle, center[3], rv[3], axis[3], co[3];
479
480         sub_v3_v3v3(vva, va, v);
481         sub_v3_v3v3(vvb, vb, v);
482         normalize_v3(vva);
483         normalize_v3(vvb);
484         angle = angle_v3v3(vva, vvb);
485
486         add_v3_v3v3(center, vva, vvb);
487         normalize_v3(center);
488         mul_v3_fl(center, offset * (1.0f / cosf(0.5f * angle)));
489         add_v3_v3(center, v);           /* coordinates of the center of the inscribed circle */
490
491
492         sub_v3_v3v3(rv, va, center);    /* radius vector */
493
494
495         sub_v3_v3v3(co, v, center);
496         cross_v3_v3v3(axis, rv, co);    /* calculate axis */
497
498         sub_v3_v3v3(vva, va, center);
499         sub_v3_v3v3(vvb, vb, center);
500         angle = angle_v3v3(vva, vvb);
501
502         rotate_v3_v3v3fl(co, rv, axis, angle * (float)(i) / (float)(count));
503
504         add_v3_v3(co, center);
505         copy_v3_v3(r, co);
506 }
507
508 /*
509  * Find the point (i/n) of the way around the round profile for e,
510  * where start point is va, midarc point is vmid, and end point is vb.
511  * Return the answer in profileco.
512  * Method:
513  * Adjust va and vb (along edge direction) so that they are perpendicular
514  * to edge at v, then use get_point_on_round_profile, then project
515  * back onto original va - vmid - vb plane.
516  * If va, vmid, and vb are all on the same plane, just interpolate between va and vb.
517  */
518 static void get_point_on_round_edge(EdgeHalf *e, int i,
519                                     float va[3], float vmid[3], float vb[3], float profileco[3])
520 {
521         float vva[3], vvb[3],  point[3], dir[3], vaadj[3], vbadj[3], p2[3], pn[3];
522         int n = e->seg;
523
524         sub_v3_v3v3(vva, va, vmid);
525         sub_v3_v3v3(vvb, vb, vmid);
526         if (e->isrev)
527                 sub_v3_v3v3(dir, e->e->v1->co, e->e->v2->co);
528         else
529                 sub_v3_v3v3(dir, e->e->v2->co, e->e->v1->co);
530         normalize_v3(dir);
531         if (fabsf(angle_v3v3(vva, vvb) - (float)M_PI) > (float)BEVEL_EPSILON) {
532                 copy_v3_v3(vaadj, va);
533                 madd_v3_v3fl(vaadj, dir, -len_v3(vva) * cosf(angle_v3v3(vva, dir)));
534                 copy_v3_v3(vbadj, vb);
535                 madd_v3_v3fl(vbadj, dir, -len_v3(vvb) * cosf(angle_v3v3(vvb, dir)));
536
537                 get_point_on_round_profile(point, e->offset, i, n, vaadj, vmid, vbadj);
538
539                 add_v3_v3v3(p2, point, dir);
540                 cross_v3_v3v3(pn, vva, vvb);
541                 if (!isect_line_plane_v3(profileco, point, p2, vmid, pn, 0)) {
542                         /* TODO: track down why this sometimes fails */
543                         copy_v3_v3(profileco, point);
544                 }
545         }
546         else {
547                 /* planar case */
548                 interp_v3_v3v3(profileco, va, vb, (float) i / (float) n);
549         }
550 }
551
552 static void mid_v3_v3v3v3(float v[3], const float v1[3], const float v2[3], const float v3[3])
553 {
554         v[0] = (v1[0] + v2[0] + v3[0]) / 3.0f;
555         v[1] = (v1[1] + v2[1] + v3[1]) / 3.0f;
556         v[2] = (v1[2] + v2[2] + v3[2]) / 3.0f;
557 }
558
559 /* Make a circular list of BoundVerts for bv, each of which has the coordinates
560  * of a vertex on the the boundary of the beveled vertex bv->v.
561  * Also decide on the mesh pattern that will be used inside the boundary.
562  * Doesn't make the actual BMVerts */
563 static void build_boundary(BevVert *bv)
564 {
565         EdgeHalf *efirst, *e;
566         BoundVert *v;
567         VMesh *vm;
568         float co[3], *no;
569         float lastd;
570
571         e = efirst = next_bev(bv, NULL);
572         vm = bv->vmesh;
573
574         BLI_assert(bv->edgecount >= 2);  /* since bevel edges incident to 2 faces */
575
576         if (bv->edgecount == 2 && bv->selcount == 1) {
577                 /* special case: beveled edge meets non-beveled one at valence 2 vert */
578                 no = e->fprev ? e->fprev->no : (e->fnext ? e->fnext->no : NULL);
579                 offset_in_plane(e, no, TRUE, co);
580                 v = add_new_bound_vert(vm, co);
581                 v->efirst = v->elast = v->ebev = e;
582                 e->leftv = v;
583                 no = e->fnext ? e->fnext->no : (e->fprev ? e->fprev->no : NULL);
584                 offset_in_plane(e, no, FALSE, co);
585                 v = add_new_bound_vert(vm, co);
586                 v->efirst = v->elast = e;
587                 e->rightv = v;
588                 /* make artifical extra point along unbeveled edge, and form triangle */
589                 slide_dist(e->next, bv->v, e->offset, co);
590                 v = add_new_bound_vert(vm, co);
591                 v->efirst = v->elast = e->next;
592                 vm->mesh_kind = M_POLY;
593                 return;
594         }
595
596         lastd = e->offset;
597         vm->boundstart = NULL;
598         do {
599                 if (e->isbev) {
600                         /* handle only left side of beveled edge e here: next iteration should do right side */
601                         if (e->prev->isbev) {
602                                 BLI_assert(e->prev != e);  /* see: wire edge special case */
603                                 offset_meet(e->prev, e, bv->v, e->fprev, TRUE, co);
604                                 v = add_new_bound_vert(vm, co);
605                                 v->efirst = e->prev;
606                                 v->elast = v->ebev = e;
607                                 e->leftv = v;
608                                 e->prev->rightv = v;
609                         }
610                         else {
611                                 /* e->prev is not beveled */
612                                 if (e->prev->prev->isbev) {
613                                         BLI_assert(e->prev->prev != e); /* see: edgecount 2, selcount 1 case */
614                                         /* find meet point between e->prev->prev and e and attach e->prev there */
615                                         /* TODO: fix case when one or both faces in following are NULL */
616                                         offset_in_two_planes(e->prev->prev, e, bv->v,
617                                                              e->prev->prev->fnext, e->fprev, co);
618                                         v = add_new_bound_vert(vm, co);
619                                         v->efirst = e->prev->prev;
620                                         v->elast = v->ebev = e;
621                                         e->leftv = v;
622                                         e->prev->leftv = v;
623                                         e->prev->prev->rightv = v;
624                                 }
625                                 else {
626                                         /* neither e->prev nor e->prev->prev are beveled: make on-edge on e->prev */
627                                         offset_meet(e->prev, e, bv->v, e->fprev, TRUE, co);
628                                         v = add_new_bound_vert(vm, co);
629                                         v->efirst = e->prev;
630                                         v->elast = v->ebev = e;
631                                         e->leftv = v;
632                                         e->prev->leftv = v;
633                                 }
634                         }
635                         lastd = len_v3v3(bv->v->co, v->nv.co);
636                 }
637                 else {
638                         /* e is not beveled */
639                         if (e->next->isbev) {
640                                 /* next iteration will place e between beveled previous and next edges */
641                                 e = e->next;
642                                 continue;
643                         }
644                         if (e->prev->isbev) {
645                                 /* on-edge meet between e->prev and e */
646                                 offset_meet(e->prev, e, bv->v, e->fprev, TRUE, co);
647                                 v = add_new_bound_vert(vm, co);
648                                 v->efirst = e->prev;
649                                 v->elast = e;
650                                 e->leftv = v;
651                                 e->prev->rightv = v;
652                         }
653                         else {
654                                 /* None of e->prev, e, e->next are beveled.
655                                  * could either leave alone or add slide points to make
656                                  * one polygon around bv->v.  For now, we choose latter.
657                                  * Could slide to make an even bevel plane but for now will
658                                  * just use last distance a meet point moved from bv->v. */
659                                 slide_dist(e, bv->v, lastd, co);
660                                 v = add_new_bound_vert(vm, co);
661                                 v->efirst = v->elast = e;
662                                 e->leftv = v;
663                         }
664                 }
665                 e = e->next;
666         } while (e != efirst);
667
668         BLI_assert(vm->count >= 2);
669         if (vm->count == 2 && bv->edgecount == 3)
670                 vm->mesh_kind = M_NONE;
671         else if (efirst->seg == 1 || bv->selcount == 1)
672                 vm->mesh_kind = M_POLY;
673         else
674                 vm->mesh_kind = M_ADJ;
675         /* TODO: if vm->count == 4 and bv->selcount == 4, use M_CROSS pattern */
676 }
677
678 /*
679  * Given that the boundary is built and the boundary BMVerts have been made,
680  * calculate the positions of the interior mesh points for the M_ADJ pattern,
681  * then make the BMVerts and the new faces. */
682 static void bevel_build_rings(BMesh *bm, BevVert *bv)
683 {
684         int k, ring, i, n, ns, ns2, nn;
685         VMesh *vm = bv->vmesh;
686         BoundVert *v, *vprev, *vnext;
687         NewVert *nv, *nvprev, *nvnext;
688         BMVert *bmv, *bmv1, *bmv2, *bmv3, *bmv4;
689         BMFace *f;
690         float co[3], coa[3], cob[3], midco[3];
691
692         n = vm->count;
693         ns = vm->seg;
694         ns2 = ns / 2;
695         BLI_assert(n > 2 && ns > 1);
696         /* Make initial rings, going between points on neighbors.
697          * After this loop, will have coords for all (i, r, k) where
698          * BoundVert for i has a bevel, 0 <= r <= ns2, 0 <= k <= ns */
699         for (ring = 1; ring <= ns2; ring++) {
700                 v = vm->boundstart;
701                 do {
702                         i = v->index;
703                         if (v->ebev) {
704                                 /* get points coords of points a and b, on outer rings
705                                  * of prev and next edges, k away from this edge */
706                                 vprev = v->prev;
707                                 vnext = v->next;
708
709                                 if (vprev->ebev)
710                                         nvprev = mesh_vert(vm, vprev->index, 0, ns - ring);
711                                 else
712                                         nvprev = mesh_vert(vm, vprev->index, 0, ns);
713                                 copy_v3_v3(coa, nvprev->co);
714                                 nv = mesh_vert(vm, i, ring, 0);
715                                 copy_v3_v3(nv->co, coa);
716                                 nv->v = nvprev->v;
717
718                                 if (vnext->ebev)
719                                         nvnext = mesh_vert(vm, vnext->index, 0, ring);
720                                 else
721                                         nvnext = mesh_vert(vm, vnext->index, 0, 0);
722                                 copy_v3_v3(cob, nvnext->co);
723                                 nv = mesh_vert(vm, i, ring, ns);
724                                 copy_v3_v3(nv->co, cob);
725                                 nv->v = nvnext->v;
726
727                                 /* TODO: better calculation of new midarc point? */
728                                 project_to_edge(v->ebev->e, coa, cob, midco);
729
730                                 for (k = 1; k < ns; k++) {
731                                         get_point_on_round_edge(v->ebev, k, coa, midco, cob, co);
732                                         copy_v3_v3(mesh_vert(vm, i, ring, k)->co, co);
733                                 }
734                         }
735                         v = v->next;
736                 } while (v != vm->boundstart);
737         }
738
739         /* Now make sure cross points of rings share coordinates and vertices.
740          * After this loop, will have BMVerts for all (i, r, k) where
741          * i is for a BoundVert that is beveled and has either a predecessor or
742          * successor BoundVert beveled too, and
743          * for odd ns: 0 <= r <= ns2, 0 <= k <= ns
744          * for even ns: 0 <= r < ns2, 0 <= k <= ns except k=ns2 */
745         v = vm->boundstart;
746         do {
747                 i = v->index;
748                 if (v->ebev) {
749                         vprev = v->prev;
750                         vnext = v->next;
751                         if (vprev->ebev) {
752                                 for (ring = 1; ring <= ns2; ring++) {
753                                         for (k = 1; k <= ns2; k++) {
754                                                 if (ns % 2 == 0 && (k == ns2 || ring == ns2))
755                                                         continue;  /* center line is special case: do after the rest are done */
756                                                 nv = mesh_vert(vm, i, ring, k);
757                                                 nvprev = mesh_vert(vm, vprev->index, k, ns - ring);
758                                                 mid_v3_v3v3(co, nv->co, nvprev->co);
759                                                 copy_v3_v3(nv->co, co);
760                                                 BLI_assert(nv->v == NULL && nvprev->v == NULL);
761                                                 create_mesh_bmvert(bm, vm, i, ring, k, bv->v);
762                                                 copy_mesh_vert(vm, vprev->index, k, ns - ring, i, ring, k);
763                                         }
764                                 }
765                                 if (!vprev->prev->ebev) {
766                                         for (ring = 1; ring <= ns2; ring++) {
767                                                 for (k = 1; k <= ns2; k++) {
768                                                         if (ns % 2 == 0 && (k == ns2 || ring == ns2))
769                                                                 continue;
770                                                         create_mesh_bmvert(bm, vm, vprev->index, ring, k, bv->v);
771                                                 }
772                                         }
773                                 }
774                                 if (!vnext->ebev) {
775                                         for (ring = 1; ring <= ns2; ring++) {
776                                                 for (k = ns - ns2; k < ns; k++) {
777                                                         if (ns % 2 == 0 && (k == ns2 || ring == ns2))
778                                                                 continue;
779                                                         create_mesh_bmvert(bm, vm, i, ring, k, bv->v);
780                                                 }
781                                         }
782                                 }
783                         }
784                 }
785                 v = v->next;
786         } while (v != vm->boundstart);
787
788         if (ns % 2 == 0) {
789                 /* Do special case center lines.
790                  * This loop makes verts for (i, ns2, k) for 1 <= k <= ns-1, k!=ns2
791                  * and for (i, r, ns2) for 1 <= r <= ns2-1,
792                  * whenever i is in a sequence of at least two beveled verts */
793                 v = vm->boundstart;
794                 do {
795                         i = v->index;
796                         if (v->ebev) {
797                                 vprev = v->prev;
798                                 vnext = v->next;
799                                 for (k = 1; k < ns2; k++) {
800                                         nv = mesh_vert(vm, i, k, ns2);
801                                         if (vprev->ebev)
802                                                 nvprev = mesh_vert(vm, vprev->index, ns2, ns - k);
803                                         if (vnext->ebev)
804                                                 nvnext = mesh_vert(vm, vnext->index, ns2, k);
805                                         if (vprev->ebev && vnext->ebev) {
806                                                 mid_v3_v3v3v3(co, nvprev->co, nv->co, nvnext->co);
807                                                 copy_v3_v3(nv->co, co);
808                                                 create_mesh_bmvert(bm, vm, i, k, ns2, bv->v);
809                                                 copy_mesh_vert(vm, vprev->index, ns2, ns - k, i, k, ns2);
810                                                 copy_mesh_vert(vm, vnext->index, ns2, k, i, k, ns2);
811
812                                         }
813                                         else if (vprev->ebev) {
814                                                 mid_v3_v3v3(co, nvprev->co, nv->co);
815                                                 copy_v3_v3(nv->co, co);
816                                                 create_mesh_bmvert(bm, vm, i, k, ns2, bv->v);
817                                                 copy_mesh_vert(vm, vprev->index, ns2, ns - k, i, k, ns2);
818
819                                                 create_mesh_bmvert(bm, vm, i, ns2, ns - k, bv->v);
820                                         }
821                                         else if (vnext->ebev) {
822                                                 mid_v3_v3v3(co, nv->co, nvnext->co);
823                                                 copy_v3_v3(nv->co, co);
824                                                 create_mesh_bmvert(bm, vm, i, k, ns2, bv->v);
825                                                 copy_mesh_vert(vm, vnext->index, ns2, k, i, k, ns2);
826
827                                                 create_mesh_bmvert(bm, vm, i, ns2, k, bv->v);
828                                         }
829                                 }
830                         }
831                         v = v->next;
832                 } while (v != vm->boundstart);
833
834                 /* center point need to be average of all centers of rings */
835                 /* TODO: this is wrong if not all verts have ebev: could have
836                  * several disconnected sections of mesh. */
837                 zero_v3(midco);
838                 nn = 0;
839                 v = vm->boundstart;
840                 do {
841                         i = v->index;
842                         if (v->ebev) {
843                                 nv = mesh_vert(vm, i, ns2, ns2);
844                                 add_v3_v3(midco, nv->co);
845                                 nn++;
846                         }
847                         v = v->next;
848                 } while (v != vm->boundstart);
849                 mul_v3_fl(midco, 1.0f / nn);
850                 bmv = BM_vert_create(bm, midco, NULL);
851                 v = vm->boundstart;
852                 do {
853                         i = v->index;
854                         if (v->ebev) {
855                                 nv = mesh_vert(vm, i, ns2, ns2);
856                                 copy_v3_v3(nv->co, midco);
857                                 nv->v = bmv;
858                         }
859                         v = v->next;
860                 } while (v != vm->boundstart);
861         }
862
863         /* Make the ring quads */
864         for (ring = 0; ring < ns2; ring++) {
865                 v = vm->boundstart;
866                 do {
867                         i = v->index;
868                         f = boundvert_rep_face(v);
869                         if (v->ebev && (v->prev->ebev || v->next->ebev)) {
870                                 for (k = 0; k < ns2 + (ns % 2); k++) {
871                                         bmv1 = mesh_vert(vm, i, ring, k)->v;
872                                         bmv2 = mesh_vert(vm, i, ring, k + 1)->v;
873                                         bmv3 = mesh_vert(vm, i, ring + 1, k + 1)->v;
874                                         bmv4 = mesh_vert(vm, i, ring + 1, k)->v;
875                                         BLI_assert(bmv1 && bmv2 && bmv3 && bmv4);
876                                         if (bmv3 == bmv4 || bmv1 == bmv4)
877                                                 bmv4 = NULL;
878                                         bev_create_quad_tri(bm, bmv1, bmv2, bmv3, bmv4, f);
879                                 }
880                         }
881                         else if (v->prev->ebev && v->prev->prev->ebev) {
882                                 /* finish off a sequence of beveled edges */
883                                 i = v->prev->index;
884                                 f = boundvert_rep_face(v->prev);
885                                 for (k = ns2 + (ns % 2); k < ns; k++) {
886                                         bmv1 = mesh_vert(vm, i, ring, k)->v;
887                                         bmv2 = mesh_vert(vm, i, ring, k + 1)->v;
888                                         bmv3 = mesh_vert(vm, i, ring + 1, k + 1)->v;
889                                         bmv4 = mesh_vert(vm, i, ring + 1, k)->v;
890                                         BLI_assert(bmv1 && bmv2 && bmv3 && bmv4);
891                                         if (bmv2 == bmv3) {
892                                                 bmv3 = bmv4;
893                                                 bmv4 = NULL;
894                                         }
895                                         bev_create_quad_tri(bm, bmv1, bmv2, bmv3, bmv4, f);
896                                 }
897                         }
898                         v = v->next;
899                 } while (v != vm->boundstart);
900         }
901
902         /* Make center ngon if odd number of segments and fully beveled */
903         if (ns % 2 == 1 && vm->count == bv->selcount) {
904                 BMVert **vv = NULL;
905                 BLI_array_declare(vv);
906
907                 v = vm->boundstart;
908                 do {
909                         i = v->index;
910                         BLI_assert(v->ebev);
911                         BLI_array_append(vv, mesh_vert(vm, i, ns2, ns2)->v);
912                         v = v->next;
913                 } while (v != vm->boundstart);
914                 f = boundvert_rep_face(vm->boundstart);
915                 bev_create_ngon(bm, vv, BLI_array_count(vv), f);
916
917                 BLI_array_free(vv);
918         }
919
920         /* Make 'rest-of-vmesh' polygon if not fully beveled */
921         if (vm->count > bv->selcount) {
922                 int j;
923                 BMVert **vv = NULL;
924                 BLI_array_declare(vv);
925
926                 v = vm->boundstart;
927                 f = boundvert_rep_face(v);
928                 j = 0;
929                 do {
930                         i = v->index;
931                         if (v->ebev) {
932                                 if (!v->prev->ebev) {
933                                         for (k = 0; k < ns2; k++) {
934                                                 bmv1 = mesh_vert(vm, i, ns2, k)->v;
935                                                 if (!bmv1)
936                                                         bmv1 = mesh_vert(vm, i, 0, k)->v;
937                                                 if (!(j > 0 && bmv1 == vv[j - 1])) {
938                                                         BLI_assert(bmv1 != NULL);
939                                                         BLI_array_append(vv, bmv1);
940                                                         j++;
941                                                 }
942                                         }
943                                 }
944                                 bmv1 = mesh_vert(vm, i, ns2, ns2)->v;
945                                 if (!bmv1)
946                                         bmv1 = mesh_vert(vm, i, 0, ns2)->v;
947                                 if (!(j > 0 && bmv1 == vv[j - 1])) {
948                                         BLI_assert(bmv1 != NULL);
949                                         BLI_array_append(vv, bmv1);
950                                         j++;
951                                 }
952                                 if (!v->next->ebev) {
953                                         for (k = ns - ns2; k < ns; k++) {
954                                                 bmv1 = mesh_vert(vm, i, ns2, k)->v;
955                                                 if (!bmv1)
956                                                         bmv1 = mesh_vert(vm, i, 0, k)->v;
957                                                 if (!(j > 0 && bmv1 == vv[j - 1])) {
958                                                         BLI_assert(bmv1 != NULL);
959                                                         BLI_array_append(vv, bmv1);
960                                                         j++;
961                                                 }
962                                         }
963                                 }
964                         }
965                         else {
966                                 BLI_assert(mesh_vert(vm, i, 0, 0)->v != NULL);
967                                 BLI_array_append(vv, mesh_vert(vm, i, 0, 0)->v);
968                                 j++;
969                         }
970                         v = v->next;
971                 } while (v != vm->boundstart);
972                 if (vv[0] == vv[j - 1])
973                         j--;
974                 bev_create_ngon(bm, vv, j, f);
975
976                 BLI_array_free(vv);
977         }
978 }
979
980 static void bevel_build_poly(BMesh *bm, BevVert *bv)
981 {
982         int n, k;
983         VMesh *vm = bv->vmesh;
984         BoundVert *v;
985         BMVert **vv = NULL;
986         BLI_array_declare(vv);
987
988         v = vm->boundstart;
989         n = 0;
990         do {
991                 /* accumulate vertices for vertex ngon */
992                 BLI_array_append(vv, v->nv.v);
993                 n++;
994                 if (v->ebev && v->ebev->seg > 1) {
995                         for (k = 1; k < v->ebev->seg; k++) {
996                                 BLI_array_append(vv, mesh_vert(vm, v->index, 0, k)->v);
997                                 n++;
998                         }
999                 }
1000                 v = v->next;
1001         } while (v != vm->boundstart);
1002         if (n > 2)
1003                 bev_create_ngon(bm, vv, n, boundvert_rep_face(v));
1004         BLI_array_free(vv);
1005 }
1006
1007 /* Given that the boundary is built, now make the actual BMVerts
1008  * for the boundary and the interior of the vertex mesh. */
1009 static void build_vmesh(BMesh *bm, BevVert *bv)
1010 {
1011         VMesh *vm = bv->vmesh;
1012         BoundVert *v, *weld1, *weld2;
1013         int n, ns, ns2, i, k, weld;
1014         float *va, *vb, co[3], midco[3];
1015
1016         n = vm->count;
1017         ns = vm->seg;
1018         ns2 = ns / 2;
1019
1020         vm->mesh = (NewVert *)MEM_callocN(n * (ns2 + 1) * (ns + 1) * sizeof(NewVert), "NewVert");
1021
1022         /* special case: two beveled ends welded together */
1023         weld = (bv->selcount == 2) && (vm->count == 2);
1024         weld1 = weld2 = NULL;   /* will hold two BoundVerts involved in weld */
1025
1026         /* make (i, 0, 0) mesh verts for all i */
1027         v = vm->boundstart;
1028         do {
1029                 i = v->index;
1030                 copy_v3_v3(mesh_vert(vm, i, 0, 0)->co, v->nv.co);
1031                 create_mesh_bmvert(bm, vm, i, 0, 0, bv->v);
1032                 v->nv.v = mesh_vert(vm, i, 0, 0)->v;
1033                 if (weld && v->ebev) {
1034                         if (!weld1)
1035                                 weld1 = v;
1036                         else
1037                                 weld2 = v;
1038                 }
1039                 v = v->next;
1040         } while (v != vm->boundstart);
1041
1042         /* copy other ends to (i, 0, ns) for all i, and fill in profiles for beveled edges */
1043         v = vm->boundstart;
1044         do {
1045                 i = v->index;
1046                 copy_mesh_vert(vm, i, 0, ns, v->next->index, 0, 0);
1047                 if (v->ebev) {
1048                         va = mesh_vert(vm, i, 0, 0)->co;
1049                         vb = mesh_vert(vm, i, 0, ns)->co;
1050                         project_to_edge(v->ebev->e, va, vb, midco);
1051                         for (k = 1; k < ns; k++) {
1052                                 get_point_on_round_edge(v->ebev, k, va, midco, vb, co);
1053                                 copy_v3_v3(mesh_vert(vm, i, 0, k)->co, co);
1054                                 if (!weld)
1055                                         create_mesh_bmvert(bm, vm, i, 0, k, bv->v);
1056                         }
1057                 }
1058                 v = v->next;
1059         } while (v != vm->boundstart);
1060
1061         if (weld) {
1062                 vm->mesh_kind = M_NONE;
1063                 for (k = 1; k < ns; k++) {
1064                         va = mesh_vert(vm, weld1->index, 0, k)->co;
1065                         vb = mesh_vert(vm, weld2->index, 0, ns - k)->co;
1066                         mid_v3_v3v3(co, va, vb);
1067                         copy_v3_v3(mesh_vert(vm, weld1->index, 0, k)->co, co);
1068                         create_mesh_bmvert(bm, vm, weld1->index, 0, k, bv->v);
1069                 }
1070                 for (k = 1; k < ns; k++)
1071                         copy_mesh_vert(vm, weld2->index, 0, ns - k, weld1->index, 0, k);
1072         }
1073
1074         if (vm->mesh_kind == M_ADJ)
1075                 bevel_build_rings(bm, bv);
1076         else if (vm->mesh_kind == M_POLY)
1077                 bevel_build_poly(bm, bv);
1078 }
1079
1080 /*
1081  * Construction around the vertex
1082  */
1083 static void bevel_vert_construct(BMesh *bm, BevelParams *bp, BMOperator *op, BMVert *v)
1084 {
1085
1086         BMOIter siter;
1087         BMEdge *bme;
1088         BevVert *bv;
1089         BMEdge *bme2, *unflagged_bme;
1090         BMFace *f;
1091         BMIter iter, iter2;
1092         EdgeHalf *e;
1093         int i, ntot, found_shared_face, ccw_test_sum;
1094         int nsel = 0;
1095
1096         /* Gather input selected edges.
1097          * Only bevel selected edges that have exactly two incident faces.
1098          *
1099          * TODO, optimization - we could tag edges in 'geom'
1100          * and then just iterate edges-of-vert, checking tags.
1101          */
1102         BMO_ITER (bme, &siter, bm, op, "geom", BM_EDGE) {
1103                 if (BM_vert_in_edge(bme, v)) {
1104                         if (BM_edge_is_manifold(bme)) {
1105                                 BMO_elem_flag_enable(bm, bme, EDGE_SELECTED);
1106                                 nsel++;
1107                         }
1108                 }
1109         }
1110
1111         if (nsel == 0)
1112                 return;
1113
1114         ntot = BM_vert_edge_count(v);
1115         bv = (BevVert *)MEM_callocN(sizeof(BevVert), "BevVert");
1116         bv->v = v;
1117         bv->edgecount = ntot;
1118         bv->selcount = nsel;
1119         bv->edges = (EdgeHalf *)MEM_callocN(ntot * sizeof(EdgeHalf), "EdgeHalf");
1120         bv->vmesh = (VMesh *)MEM_callocN(sizeof(VMesh), "VMesh");
1121         bv->vmesh->seg = bp->seg;
1122         BLI_addtail(&bp->vertList, bv);
1123
1124         /* add edges to bv->edges in order that keeps adjacent edges sharing
1125          * a face, if possible */
1126         i = 0;
1127         bme = v->e;
1128         BMO_elem_flag_enable(bm, bme, BEVEL_FLAG);
1129         e = &bv->edges[0];
1130         e->e = bme;
1131         for (i = 0; i < ntot; i++) {
1132                 if (i > 0) {
1133                         /* find an unflagged edge bme2 that shares a face f with previous bme */
1134                         found_shared_face = 0;
1135                         unflagged_bme = NULL;
1136                         BM_ITER_ELEM (bme2, &iter, v, BM_EDGES_OF_VERT) {
1137                                 if (BMO_elem_flag_test(bm, bme2, BEVEL_FLAG))
1138                                         continue;
1139                                 if (!unflagged_bme)
1140                                         unflagged_bme = bme2;
1141                                 BM_ITER_ELEM (f, &iter2, bme2, BM_FACES_OF_EDGE) {
1142                                         if (BM_face_edge_share_loop(f, bme)) {
1143                                                 found_shared_face = 1;
1144                                                 break;
1145                                         }
1146                                 }
1147                                 if (found_shared_face)
1148                                         break;
1149                         }
1150                         e = &bv->edges[i];
1151                         if (found_shared_face) {
1152                                 e->e = bme2;
1153                                 e->fprev = f;
1154                                 bv->edges[i - 1].fnext = f;
1155                         }
1156                         else {
1157                                 e->e = unflagged_bme;
1158                         }
1159                 }
1160                 bme = e->e;
1161                 BMO_elem_flag_enable(bm, bme, BEVEL_FLAG);
1162                 if (BMO_elem_flag_test(bm, bme, EDGE_SELECTED)) {
1163                         e->isbev = 1;
1164                         e->seg = bp->seg;
1165                 }
1166                 else {
1167                         e->isbev = 0;
1168                         e->seg = 0;
1169                 }
1170                 e->isrev = (bme->v2 == v);
1171                 e->offset = e->isbev ? bp->offset : 0.0f;
1172         }
1173         /* find wrap-around shared face */
1174         BM_ITER_ELEM (f, &iter2, bme, BM_FACES_OF_EDGE) {
1175                 if (BM_face_edge_share_loop(f, bv->edges[0].e)) {
1176                         if (bv->edges[0].fnext == f)
1177                                 continue;   /* if two shared faces, want the other one now */
1178                         bv->edges[ntot - 1].fnext = f;
1179                         bv->edges[0].fprev = f;
1180                         break;
1181                 }
1182         }
1183
1184         /* remove BEVEL_FLAG now that we are finished with it*/
1185         for (i = 0; i < ntot; i++)
1186                 BMO_elem_flag_disable(bm, bv->edges[i].e, BEVEL_FLAG);
1187
1188         /* if edge array doesn't go CCW around vertex from average normal side,
1189          * reverse the array, being careful to reverse face pointers too */
1190         if (ntot > 1) {
1191                 ccw_test_sum = 0;
1192                 for (i = 0; i < ntot; i++)
1193                         ccw_test_sum += bev_ccw_test(bv->edges[i].e, bv->edges[(i + 1) % ntot].e,
1194                                                      bv->edges[i].fnext);
1195                 if (ccw_test_sum < 0) {
1196                         for (i = 0; i <= (ntot / 2) - 1; i++) {
1197                                 SWAP(EdgeHalf, bv->edges[i], bv->edges[ntot - i - 1]);
1198                                 SWAP(BMFace *, bv->edges[i].fprev, bv->edges[i].fnext);
1199                                 SWAP(BMFace *, bv->edges[ntot - i - 1].fprev, bv->edges[ntot - i - 1].fnext);
1200                         }
1201                         if (ntot % 2 == 1) {
1202                                 i = ntot / 2;
1203                                 SWAP(BMFace *, bv->edges[i].fprev,  bv->edges[i].fnext);
1204                         }
1205                 }
1206         }
1207
1208         for (i = 0; i < ntot; i++) {
1209                 e = &bv->edges[i];
1210                 e->next = &bv->edges[(i + 1) % ntot];
1211                 e->prev = &bv->edges[(i + ntot - 1) % ntot];
1212         }
1213
1214         build_boundary(bv);
1215         build_vmesh(bm, bv);
1216 }
1217
1218 /* Face f has at least one beveled vertex.  Rebuild f */
1219 static void rebuild_polygon(BMesh *bm, BevelParams *bp, BMFace *f)
1220 {
1221         BMIter liter;
1222         BMLoop *l, *lprev;
1223         BevVert *bv;
1224         BoundVert *v, *vstart, *vend;
1225         EdgeHalf *e, *eprev;
1226         VMesh *vm;
1227         int i, k;
1228         BMVert *bmv;
1229         BMVert **vv = NULL;
1230         BLI_array_declare(vv);
1231
1232         BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
1233                 bv = find_bevvert(bp, l->v);
1234                 if (bv) {
1235                         lprev = l->prev;
1236                         e = find_edge_half(bv, l->e);
1237                         eprev = find_edge_half(bv, lprev->e);
1238                         BLI_assert(e != NULL && eprev != NULL);
1239                         vstart = eprev->leftv;
1240                         if (e->isbev)
1241                                 vend = e->rightv;
1242                         else
1243                                 vend = e->leftv;
1244                         v = vstart;
1245                         vm = bv->vmesh;
1246                         BLI_array_append(vv, v->nv.v);
1247                         while (v != vend) {
1248                                 if (vm->mesh_kind == M_NONE && v->ebev && v->ebev->seg > 1 && v->ebev != e && v->ebev != eprev) {
1249                                         /* case of 3rd face opposite a beveled edge, with no vmesh */
1250                                         i = v->index;
1251                                         e = v->ebev;
1252                                         for (k = 1; k < e->seg; k++) {
1253                                                 bmv = mesh_vert(vm, i, 0, k)->v;
1254                                                 BLI_array_append(vv, bmv);
1255                                         }
1256                                 }
1257                                 v = v->prev;
1258                                 BLI_array_append(vv, v->nv.v);
1259                         }
1260                 }
1261                 else {
1262                         BLI_array_append(vv, l->v);
1263                 }
1264         }
1265         bev_create_ngon(bm, vv, BLI_array_count(vv), f);
1266         BLI_array_free(vv);
1267 }
1268
1269 /* All polygons touching v need rebuilding because beveling v has made new vertices */
1270 static void bevel_rebuild_existing_polygons(BMesh *bm, BevelParams *bp, BMVert *v)
1271 {
1272         void    *faces_stack[BM_DEFAULT_ITER_STACK_SIZE];
1273         int      faces_len, f_index;
1274         BMFace **faces = BM_iter_as_arrayN(bm, BM_FACES_OF_VERT, v, &faces_len,
1275                                            faces_stack, BM_DEFAULT_ITER_STACK_SIZE);
1276
1277         if (LIKELY(faces != NULL)) {
1278                 for (f_index = 0; f_index < faces_len; f_index++) {
1279                         BMFace *f = faces[f_index];
1280                         rebuild_polygon(bm, bp, f);
1281                         BM_face_kill(bm, f);
1282                 }
1283
1284                 if (faces != (BMFace **)faces_stack) {
1285                         MEM_freeN(faces);
1286                 }
1287         }
1288 }
1289
1290
1291
1292 /*
1293  * Build the polygons along the selected Edge
1294  */
1295 static void bevel_build_edge_polygons(BMesh *bm, BevelParams *bp, BMEdge *bme)
1296 {
1297         BevVert *bv1, *bv2;
1298         BMVert *bmv1, *bmv2, *bmv3, *bmv4, *bmv1i, *bmv2i, *bmv3i, *bmv4i;
1299         VMesh *vm1, *vm2;
1300         EdgeHalf *e1, *e2;
1301         BMFace *f1, *f2, *f;
1302         int k, nseg, i1, i2;
1303
1304         if (!BM_edge_is_manifold(bme))
1305                 return;
1306
1307         bv1 = find_bevvert(bp, bme->v1);
1308         bv2 = find_bevvert(bp, bme->v2);
1309
1310         BLI_assert(bv1 && bv2);
1311
1312         e1 = find_edge_half(bv1, bme);
1313         e2 = find_edge_half(bv2, bme);
1314
1315         BLI_assert(e1 && e2);
1316
1317         /*   v4             v3
1318          *    \            /
1319          *     e->v1 - e->v2
1320          *    /            \
1321          *   v1             v2
1322          */
1323         nseg = e1->seg;
1324         BLI_assert(nseg > 0 && nseg == e2->seg);
1325
1326         bmv1 = e1->leftv->nv.v;
1327         bmv4 = e1->rightv->nv.v;
1328         bmv2 = e2->rightv->nv.v;
1329         bmv3 = e2->leftv->nv.v;
1330
1331         BLI_assert(bmv1 && bmv2 && bmv3 && bmv4);
1332
1333         f1 = boundvert_rep_face(e1->leftv);
1334         f2 = boundvert_rep_face(e1->rightv);
1335
1336         if (nseg == 1) {
1337                 bev_create_quad_tri(bm, bmv1, bmv2, bmv3, bmv4, f1);
1338         }
1339         else {
1340                 i1 = e1->leftv->index;
1341                 i2 = e2->leftv->index;
1342                 vm1 = bv1->vmesh;
1343                 vm2 = bv2->vmesh;
1344                 bmv1i = bmv1;
1345                 bmv2i = bmv2;
1346                 for (k = 1; k <= nseg; k++) {
1347                         bmv4i = mesh_vert(vm1, i1, 0, k)->v;
1348                         bmv3i = mesh_vert(vm2, i2, 0, nseg - k)->v;
1349                         f = (k <= nseg / 2 + (nseg % 2)) ? f1 : f2;
1350                         bev_create_quad_tri(bm, bmv1i, bmv2i, bmv3i, bmv4i, f);
1351                         bmv1i = bmv4i;
1352                         bmv2i = bmv3i;
1353                 }
1354         }
1355 }
1356
1357
1358 static void free_bevel_params(BevelParams *bp)
1359 {
1360         BevVert *bv;
1361         VMesh *vm;
1362         BoundVert *v, *vnext;
1363
1364         for (bv = bp->vertList.first; bv; bv = bv->next) {
1365                 MEM_freeN(bv->edges);
1366                 vm = bv->vmesh;
1367                 v = vm->boundstart;
1368                 if (v) {
1369                         do {
1370                                 vnext = v->next;
1371                                 MEM_freeN(v);
1372                                 v = vnext;
1373                         } while (v != vm->boundstart);
1374                 }
1375                 if (vm->mesh)
1376                         MEM_freeN(vm->mesh);
1377                 MEM_freeN(vm);
1378         }
1379         BLI_freelistN(&bp->vertList);
1380 }
1381
1382 void bmo_bevel_exec(BMesh *bm, BMOperator *op)
1383 {
1384         BMOIter siter;
1385         BMVert *v;
1386         BMEdge *e;
1387         BevelParams bp = {{NULL}};
1388
1389         bp.offset = BMO_slot_float_get(op, "offset");
1390         bp.op = op;
1391         bp.seg = BMO_slot_int_get(op, "segments");
1392
1393         if (bp.offset > 0) {
1394                 /* The analysis of the input vertices and execution additional constructions */
1395                 BMO_ITER (v, &siter, bm, op, "geom", BM_VERT) {
1396                         bevel_vert_construct(bm, &bp, op, v);
1397                 }
1398                 /* Build polygons for edges */
1399                 BMO_ITER (e, &siter, bm, op, "geom", BM_EDGE) {
1400                         bevel_build_edge_polygons(bm, &bp, e);
1401                 }
1402
1403                 BMO_ITER (v, &siter, bm, op, "geom", BM_VERT) {
1404                         bevel_rebuild_existing_polygons(bm, &bp, v);
1405                 }
1406
1407                 BMO_ITER (v, &siter, bm, op, "geom", BM_VERT) {
1408                         if (find_bevvert(&bp, v))
1409                                 BM_vert_kill(bm, v);
1410                 }
1411                 free_bevel_params(&bp);
1412         }
1413
1414 }
1415
1416 #else
1417 #define BEVEL_FLAG  1
1418 #define BEVEL_DEL   2
1419 #define FACE_NEW    4
1420 #define EDGE_OLD    8
1421 #define FACE_OLD    16
1422 #define VERT_OLD    32
1423 #define FACE_SPAN   64
1424 #define FACE_HOLE   128
1425
1426 typedef struct LoopTag {
1427         BMVert *newv;
1428 } LoopTag;
1429
1430 typedef struct EdgeTag {
1431         BMVert *newv1, *newv2;
1432 } EdgeTag;
1433
1434 static void calc_corner_co(BMLoop *l, const float fac, float r_co[3],
1435                            const short do_dist, const short do_even)
1436 {
1437         float no[3], l_vec_prev[3], l_vec_next[3], l_co_prev[3], l_co[3], l_co_next[3], co_ofs[3];
1438         int is_concave;
1439
1440         /* first get the prev/next verts */
1441         if (l->f->len > 2) {
1442                 copy_v3_v3(l_co_prev, l->prev->v->co);
1443                 copy_v3_v3(l_co, l->v->co);
1444                 copy_v3_v3(l_co_next, l->next->v->co);
1445
1446                 /* calculate normal */
1447                 sub_v3_v3v3(l_vec_prev, l_co_prev, l_co);
1448                 sub_v3_v3v3(l_vec_next, l_co_next, l_co);
1449
1450                 cross_v3_v3v3(no, l_vec_prev, l_vec_next);
1451                 is_concave = dot_v3v3(no, l->f->no) > 0.0f;
1452         }
1453         else {
1454                 BMIter iter;
1455                 BMLoop *l2;
1456                 float up[3] = {0.0f, 0.0f, 1.0f};
1457
1458                 copy_v3_v3(l_co_prev, l->prev->v->co);
1459                 copy_v3_v3(l_co, l->v->co);
1460                 
1461                 BM_ITER_ELEM (l2, &iter, l->v, BM_LOOPS_OF_VERT) {
1462                         if (l2->f != l->f) {
1463                                 copy_v3_v3(l_co_next, BM_edge_other_vert(l2->e, l2->next->v)->co);
1464                                 break;
1465                         }
1466                 }
1467                 
1468                 sub_v3_v3v3(l_vec_prev, l_co_prev, l_co);
1469                 sub_v3_v3v3(l_vec_next, l_co_next, l_co);
1470
1471                 cross_v3_v3v3(no, l_vec_prev, l_vec_next);
1472                 if (dot_v3v3(no, no) == 0.0f) {
1473                         no[0] = no[1] = 0.0f; no[2] = -1.0f;
1474                 }
1475                 
1476                 is_concave = dot_v3v3(no, up) < 0.0f;
1477         }
1478
1479
1480         /* now calculate the new location */
1481         if (do_dist) { /* treat 'fac' as distance */
1482
1483                 normalize_v3(l_vec_prev);
1484                 normalize_v3(l_vec_next);
1485
1486                 add_v3_v3v3(co_ofs, l_vec_prev, l_vec_next);
1487                 if (UNLIKELY(normalize_v3(co_ofs) == 0.0f)) {  /* edges form a straight line */
1488                         cross_v3_v3v3(co_ofs, l_vec_prev, l->f->no);
1489                 }
1490
1491                 if (do_even) {
1492                         negate_v3(l_vec_next);
1493                         mul_v3_fl(co_ofs, fac * shell_angle_to_dist(0.5f * angle_normalized_v3v3(l_vec_prev, l_vec_next)));
1494                         /* negate_v3(l_vec_next); */ /* no need unless we use again */
1495                 }
1496                 else {
1497                         mul_v3_fl(co_ofs, fac);
1498                 }
1499         }
1500         else { /* treat as 'fac' as a factor (0 - 1) */
1501
1502                 /* not strictly necessary, balance vectors
1503                  * so the longer edge doesn't skew the result,
1504                  * gives nicer, move even output.
1505                  *
1506                  * Use the minimum rather then the middle value so skinny faces don't flip along the short axis */
1507                 float min_fac = min_ff(normalize_v3(l_vec_prev), normalize_v3(l_vec_next));
1508                 float angle;
1509
1510                 if (do_even) {
1511                         negate_v3(l_vec_next);
1512                         angle = angle_normalized_v3v3(l_vec_prev, l_vec_next);
1513                         negate_v3(l_vec_next); /* no need unless we use again */
1514                 }
1515                 else {
1516                         angle = 0.0f;
1517                 }
1518
1519                 mul_v3_fl(l_vec_prev, min_fac);
1520                 mul_v3_fl(l_vec_next, min_fac);
1521
1522                 add_v3_v3v3(co_ofs, l_vec_prev, l_vec_next);
1523
1524                 if (UNLIKELY(is_zero_v3(co_ofs))) {
1525                         cross_v3_v3v3(co_ofs, l_vec_prev, l->f->no);
1526                         normalize_v3(co_ofs);
1527                         mul_v3_fl(co_ofs, min_fac);
1528                 }
1529
1530                 /* done */
1531                 if (do_even) {
1532                         mul_v3_fl(co_ofs, (fac * 0.5f) * shell_angle_to_dist(0.5f * angle));
1533                 }
1534                 else {
1535                         mul_v3_fl(co_ofs, fac * 0.5f);
1536                 }
1537         }
1538
1539         /* apply delta vec */
1540         if (is_concave)
1541                 negate_v3(co_ofs);
1542
1543         add_v3_v3v3(r_co, co_ofs, l->v->co);
1544 }
1545
1546
1547 #define ETAG_SET(e, v, nv)  (                                                 \
1548         (v) == (e)->v1 ?                                                          \
1549                 (etags[BM_elem_index_get((e))].newv1 = (nv)) :                        \
1550                 (etags[BM_elem_index_get((e))].newv2 = (nv))                          \
1551         )
1552
1553 #define ETAG_GET(e, v)  (                                                     \
1554         (v) == (e)->v1 ?                                                          \
1555                 (etags[BM_elem_index_get((e))].newv1) :                               \
1556                 (etags[BM_elem_index_get((e))].newv2)                                 \
1557         )
1558
1559 void bmo_bevel_exec(BMesh *bm, BMOperator *op)
1560 {
1561         BMOIter siter;
1562         BMIter iter;
1563         BMEdge *e;
1564         BMVert *v;
1565         BMFace **faces = NULL, *f;
1566         LoopTag *tags = NULL, *tag;
1567         EdgeTag *etags = NULL;
1568         BMVert **verts = NULL;
1569         BMEdge **edges = NULL;
1570         BLI_array_declare(faces);
1571         BLI_array_declare(tags);
1572         BLI_array_declare(etags);
1573         BLI_array_declare(verts);
1574         BLI_array_declare(edges);
1575         SmallHash hash;
1576         float fac = BMO_slot_float_get(op, "percent");
1577         const short do_even = BMO_slot_bool_get(op, "use_even");
1578         const short do_dist = BMO_slot_bool_get(op, "use_dist");
1579         int i, li, has_elens, HasMDisps = CustomData_has_layer(&bm->ldata, CD_MDISPS);
1580         
1581         has_elens = CustomData_has_layer(&bm->edata, CD_PROP_FLT) && BMO_slot_bool_get(op, "use_lengths");
1582         if (has_elens) {
1583                 li = BMO_slot_int_get(op, "lengthlayer");
1584         }
1585         
1586         BLI_smallhash_init(&hash);
1587         
1588         BMO_ITER (e, &siter, bm, op, "geom", BM_EDGE) {
1589                 BMO_elem_flag_enable(bm, e, BEVEL_FLAG | BEVEL_DEL);
1590                 BMO_elem_flag_enable(bm, e->v1, BEVEL_FLAG | BEVEL_DEL);
1591                 BMO_elem_flag_enable(bm, e->v2, BEVEL_FLAG | BEVEL_DEL);
1592                 
1593                 if (BM_edge_face_count(e) < 2) {
1594                         BMO_elem_flag_disable(bm, e, BEVEL_DEL);
1595                         BMO_elem_flag_disable(bm, e->v1, BEVEL_DEL);
1596                         BMO_elem_flag_disable(bm, e->v2, BEVEL_DEL);
1597                 }
1598 #if 0
1599                 if (BM_edge_is_wire(e)) {
1600                         BMVert *verts[2] = {e->v1, e->v2};
1601                         BMEdge *edges[2] = {e, BM_edge_create(bm, e->v1, e->v2, e, 0)};
1602                         
1603                         BMO_elem_flag_enable(bm, edges[1], BEVEL_FLAG);
1604                         BM_face_create(bm, verts, edges, 2, FALSE);
1605                 }
1606 #endif
1607         }
1608         
1609         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
1610                 BMO_elem_flag_enable(bm, v, VERT_OLD);
1611         }
1612
1613 #if 0
1614         /* a bit of cleaner code that, alas, doens't work. */
1615         /* build edge tag */
1616         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
1617                 if (BMO_elem_flag_test(bm, e->v1, BEVEL_FLAG) || BMO_elem_flag_test(bm, e->v2, BEVEL_FLAG)) {
1618                         BMIter liter;
1619                         BMLoop *l;
1620                         
1621                         if (!BMO_elem_flag_test(bm, e, EDGE_OLD)) {
1622                                 BM_elem_index_set(e, BLI_array_count(etags)); /* set_dirty! */
1623                                 BLI_array_grow_one(etags);
1624                                 
1625                                 BMO_elem_flag_enable(bm, e, EDGE_OLD);
1626                         }
1627                         
1628                         BM_ITER_ELEM (l, &liter, e, BM_LOOPS_OF_EDGE) {
1629                                 BMLoop *l2;
1630                                 BMIter liter2;
1631                                 
1632                                 if (BMO_elem_flag_test(bm, l->f, BEVEL_FLAG))
1633                                         continue;
1634
1635                                 BM_ITER_ELEM (l2, &liter2, l->f, BM_LOOPS_OF_FACE) {
1636                                         BM_elem_index_set(l2, BLI_array_count(tags)); /* set_loop */
1637                                         BLI_array_grow_one(tags);
1638
1639                                         if (!BMO_elem_flag_test(bm, l2->e, EDGE_OLD)) {
1640                                                 BM_elem_index_set(l2->e, BLI_array_count(etags)); /* set_dirty! */
1641                                                 BLI_array_grow_one(etags);
1642                                                 
1643                                                 BMO_elem_flag_enable(bm, l2->e, EDGE_OLD);
1644                                         }
1645                                 }
1646
1647                                 BMO_elem_flag_enable(bm, l->f, BEVEL_FLAG);
1648                                 BLI_array_append(faces, l->f);
1649                         }
1650                 }
1651                 else {
1652                         BM_elem_index_set(e, -1); /* set_dirty! */
1653                 }
1654         }
1655 #endif
1656         
1657         /* create and assign looptag structure */
1658         BMO_ITER (e, &siter, bm, op, "geom", BM_EDGE) {
1659                 BMLoop *l;
1660                 BMIter liter;
1661
1662                 BMO_elem_flag_enable(bm, e->v1, BEVEL_FLAG | BEVEL_DEL);
1663                 BMO_elem_flag_enable(bm, e->v2, BEVEL_FLAG | BEVEL_DEL);
1664                 
1665                 if (BM_edge_face_count(e) < 2) {
1666                         BMO_elem_flag_disable(bm, e, BEVEL_DEL);
1667                         BMO_elem_flag_disable(bm, e->v1, BEVEL_DEL);
1668                         BMO_elem_flag_disable(bm, e->v2, BEVEL_DEL);
1669                 }
1670                 
1671                 if (!BLI_smallhash_haskey(&hash, (intptr_t)e)) {
1672                         BLI_array_grow_one(etags);
1673                         BM_elem_index_set(e, BLI_array_count(etags) - 1); /* set_dirty! */
1674                         BLI_smallhash_insert(&hash, (intptr_t)e, NULL);
1675                         BMO_elem_flag_enable(bm, e, EDGE_OLD);
1676                 }
1677                 
1678                 /* find all faces surrounding e->v1 and, e->v2 */
1679                 for (i = 0; i < 2; i++) {
1680                         BM_ITER_ELEM (l, &liter, i ? e->v2 : e->v1, BM_LOOPS_OF_VERT) {
1681                                 BMLoop *l2;
1682                                 BMIter liter2;
1683                                 
1684                                 /* see if we've already processed this loop's fac */
1685                                 if (BLI_smallhash_haskey(&hash, (intptr_t)l->f))
1686                                         continue;
1687                                 
1688                                 /* create tags for all loops in l-> */
1689                                 BM_ITER_ELEM (l2, &liter2, l->f, BM_LOOPS_OF_FACE) {
1690                                         BLI_array_grow_one(tags);
1691                                         BM_elem_index_set(l2, BLI_array_count(tags) - 1); /* set_loop */
1692                                         
1693                                         if (!BLI_smallhash_haskey(&hash, (intptr_t)l2->e)) {
1694                                                 BLI_array_grow_one(etags);
1695                                                 BM_elem_index_set(l2->e, BLI_array_count(etags) - 1); /* set_dirty! */
1696                                                 BLI_smallhash_insert(&hash, (intptr_t)l2->e, NULL);
1697                                                 BMO_elem_flag_enable(bm, l2->e, EDGE_OLD);
1698                                         }
1699                                 }
1700
1701                                 BLI_smallhash_insert(&hash, (intptr_t)l->f, NULL);
1702                                 BMO_elem_flag_enable(bm, l->f, BEVEL_FLAG);
1703                                 BLI_array_append(faces, l->f);
1704                         }
1705                 }
1706         }
1707
1708         bm->elem_index_dirty |= BM_EDGE;
1709         
1710         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
1711                 BMIter eiter;
1712                 
1713                 if (!BMO_elem_flag_test(bm, v, BEVEL_FLAG))
1714                         continue;
1715                 
1716                 BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
1717                         if (!BMO_elem_flag_test(bm, e, BEVEL_FLAG) && !ETAG_GET(e, v)) {
1718                                 BMVert *v2;
1719                                 float co[3];
1720                                 
1721                                 v2 = BM_edge_other_vert(e, v);
1722                                 sub_v3_v3v3(co, v2->co, v->co);
1723                                 if (has_elens) {
1724                                         float elen = *(float *)CustomData_bmesh_get_n(&bm->edata, e->head.data, CD_PROP_FLT, li);
1725
1726                                         normalize_v3(co);
1727                                         mul_v3_fl(co, elen);
1728                                 }
1729                                 
1730                                 mul_v3_fl(co, fac);
1731                                 add_v3_v3(co, v->co);
1732                                 
1733                                 v2 = BM_vert_create(bm, co, v);
1734                                 ETAG_SET(e, v, v2);
1735                         }
1736                 }
1737         }
1738         
1739         for (i = 0; i < BLI_array_count(faces); i++) {
1740                 BMLoop *l;
1741                 BMIter liter;
1742                 
1743                 BMO_elem_flag_enable(bm, faces[i], FACE_OLD);
1744                 
1745                 BM_ITER_ELEM (l, &liter, faces[i], BM_LOOPS_OF_FACE) {
1746                         float co[3];
1747
1748                         if (BMO_elem_flag_test(bm, l->e, BEVEL_FLAG)) {
1749                                 if (BMO_elem_flag_test(bm, l->prev->e, BEVEL_FLAG)) {
1750                                         tag = tags + BM_elem_index_get(l);
1751                                         calc_corner_co(l, fac, co, do_dist, do_even);
1752                                         tag->newv = BM_vert_create(bm, co, l->v);
1753                                 }
1754                                 else {
1755                                         tag = tags + BM_elem_index_get(l);
1756                                         tag->newv = ETAG_GET(l->prev->e, l->v);
1757                                         
1758                                         if (!tag->newv) {
1759                                                 sub_v3_v3v3(co, l->prev->v->co, l->v->co);
1760                                                 if (has_elens) {
1761                                                         float elen = *(float *)CustomData_bmesh_get_n(&bm->edata, l->prev->e->head.data,
1762                                                                                                       CD_PROP_FLT, li);
1763
1764                                                         normalize_v3(co);
1765                                                         mul_v3_fl(co, elen);
1766                                                 }
1767
1768                                                 mul_v3_fl(co, fac);
1769                                                 add_v3_v3(co, l->v->co);
1770
1771                                                 tag->newv = BM_vert_create(bm, co, l->v);
1772                                                 
1773                                                 ETAG_SET(l->prev->e, l->v, tag->newv);
1774                                         }
1775                                 }
1776                         }
1777                         else if (BMO_elem_flag_test(bm, l->v, BEVEL_FLAG)) {
1778                                 tag = tags + BM_elem_index_get(l);
1779                                 tag->newv = ETAG_GET(l->e, l->v);
1780
1781                                 if (!tag->newv) {
1782                                         sub_v3_v3v3(co, l->next->v->co, l->v->co);
1783                                         if (has_elens) {
1784                                                 float elen = *(float *)CustomData_bmesh_get_n(&bm->edata, l->e->head.data, CD_PROP_FLT, li);
1785
1786                                                 normalize_v3(co);
1787                                                 mul_v3_fl(co, elen);
1788                                         }
1789                                         
1790                                         mul_v3_fl(co, fac);
1791                                         add_v3_v3(co, l->v->co);
1792
1793                                         tag = tags + BM_elem_index_get(l);
1794                                         tag->newv = BM_vert_create(bm, co, l->v);
1795                                         
1796                                         ETAG_SET(l->e, l->v, tag->newv);
1797                                 }
1798                         }
1799                         else {
1800                                 tag = tags + BM_elem_index_get(l);
1801                                 tag->newv = l->v;
1802                                 BMO_elem_flag_disable(bm, l->v, BEVEL_DEL);
1803                         }
1804                 }
1805         }
1806         
1807         /* create new faces inset from original face */
1808         for (i = 0; i < BLI_array_count(faces); i++) {
1809                 BMLoop *l;
1810                 BMIter liter;
1811                 BMFace *f;
1812                 BMVert *lastv = NULL, *firstv = NULL;
1813
1814                 BMO_elem_flag_enable(bm, faces[i], BEVEL_DEL);
1815                 
1816                 BLI_array_empty(verts);
1817                 BLI_array_empty(edges);
1818                 
1819                 BM_ITER_ELEM (l, &liter, faces[i], BM_LOOPS_OF_FACE) {
1820                         BMVert *v2;
1821                         
1822                         tag = tags + BM_elem_index_get(l);
1823                         BLI_array_append(verts, tag->newv);
1824                         
1825                         if (!firstv)
1826                                 firstv = tag->newv;
1827                         
1828                         if (lastv) {
1829                                 e = BM_edge_create(bm, lastv, tag->newv, l->e, TRUE);
1830                                 BM_elem_attrs_copy(bm, bm, l->prev->e, e);
1831                                 BLI_array_append(edges, e);
1832                         }
1833                         lastv = tag->newv;
1834                         
1835                         v2 = ETAG_GET(l->e, l->next->v);
1836                         
1837                         tag = &tags[BM_elem_index_get(l->next)];
1838                         if (!BMO_elem_flag_test(bm, l->e, BEVEL_FLAG) && v2 && v2 != tag->newv) {
1839                                 BLI_array_append(verts, v2);
1840                                 
1841                                 e = BM_edge_create(bm, lastv, v2, l->e, TRUE);
1842                                 BM_elem_attrs_copy(bm, bm, l->e, e);
1843                                 
1844                                 BLI_array_append(edges, e);
1845                                 lastv = v2;
1846                         }
1847                 }
1848                 
1849                 e = BM_edge_create(bm, firstv, lastv, BM_FACE_FIRST_LOOP(faces[i])->e, TRUE);
1850                 if (BM_FACE_FIRST_LOOP(faces[i])->prev->e != e) {
1851                         BM_elem_attrs_copy(bm, bm, BM_FACE_FIRST_LOOP(faces[i])->prev->e, e);
1852                 }
1853                 BLI_array_append(edges, e);
1854                 
1855                 f = BM_face_create_ngon(bm, verts[0], verts[1], edges, BLI_array_count(edges), FALSE);
1856                 if (UNLIKELY(f == NULL)) {
1857                         printf("%s: could not make face!\n", __func__);
1858                         continue;
1859                 }
1860
1861                 BMO_elem_flag_enable(bm, f, FACE_NEW);
1862         }
1863
1864         for (i = 0; i < BLI_array_count(faces); i++) {
1865                 BMLoop *l;
1866                 BMIter liter;
1867                 int j;
1868                 
1869                 /* create quad spans between split edge */
1870                 BM_ITER_ELEM (l, &liter, faces[i], BM_LOOPS_OF_FACE) {
1871                         BMVert *v1 = NULL, *v2 = NULL, *v3 = NULL, *v4 = NULL;
1872                         
1873                         if (!BMO_elem_flag_test(bm, l->e, BEVEL_FLAG))
1874                                 continue;
1875                         
1876                         v1 = tags[BM_elem_index_get(l)].newv;
1877                         v2 = tags[BM_elem_index_get(l->next)].newv;
1878                         if (l->radial_next != l) {
1879                                 v3 = tags[BM_elem_index_get(l->radial_next)].newv;
1880                                 if (l->radial_next->next->v == l->next->v) {
1881                                         v4 = v3;
1882                                         v3 = tags[BM_elem_index_get(l->radial_next->next)].newv;
1883                                 }
1884                                 else {
1885                                         v4 = tags[BM_elem_index_get(l->radial_next->next)].newv;
1886                                 }
1887                         }
1888                         else {
1889                                 /* the loop is on a boundar */
1890                                 v3 = l->next->v;
1891                                 v4 = l->v;
1892                                 
1893                                 for (j = 0; j < 2; j++) {
1894                                         BMIter eiter;
1895                                         BMVert *v = j ? v4 : v3;
1896
1897                                         BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
1898                                                 if (!BM_vert_in_edge(e, v3) || !BM_vert_in_edge(e, v4))
1899                                                         continue;
1900                                                 
1901                                                 if (!BMO_elem_flag_test(bm, e, BEVEL_FLAG) && BMO_elem_flag_test(bm, e, EDGE_OLD)) {
1902                                                         BMVert *vv;
1903                                                         
1904                                                         vv = ETAG_GET(e, v);
1905                                                         if (!vv || BMO_elem_flag_test(bm, vv, BEVEL_FLAG))
1906                                                                 continue;
1907                                                         
1908                                                         if (j) {
1909                                                                 v1 = vv;
1910                                                         }
1911                                                         else {
1912                                                                 v2 = vv;
1913                                                         }
1914                                                         break;
1915                                                 }
1916                                         }
1917                                 }
1918
1919                                 BMO_elem_flag_disable(bm, v3, BEVEL_DEL);
1920                                 BMO_elem_flag_disable(bm, v4, BEVEL_DEL);
1921                         }
1922                         
1923                         if (v1 != v2 && v2 != v3 && v3 != v4) {
1924                                 BMIter liter2;
1925                                 BMLoop *l2, *l3;
1926                                 BMEdge *e1, *e2;
1927                                 float d1, d2, *d3;
1928                                 
1929                                 f = BM_face_create_quad_tri(bm, v4, v3, v2, v1, l->f, TRUE);
1930
1931                                 e1 = BM_edge_exists(v4, v3);
1932                                 e2 = BM_edge_exists(v2, v1);
1933                                 BM_elem_attrs_copy(bm, bm, l->e, e1);
1934                                 BM_elem_attrs_copy(bm, bm, l->e, e2);
1935                                 
1936                                 /* set edge lengths of cross edges as the average of the cross edges they're based o */
1937                                 if (has_elens) {
1938                                         /* angle happens not to be used. why? - not sure it just isn't - campbell.
1939                                          * leave this in in case we need to use it later */
1940 #if 0
1941                                         float ang;
1942 #endif
1943                                         e1 = BM_edge_exists(v1, v4);
1944                                         e2 = BM_edge_exists(v2, v3);
1945                                         
1946                                         if (l->radial_next->v == l->v) {
1947                                                 l2 = l->radial_next->prev;
1948                                                 l3 = l->radial_next->next;
1949                                         }
1950                                         else {
1951                                                 l2 = l->radial_next->next;
1952                                                 l3 = l->radial_next->prev;
1953                                         }
1954                                         
1955                                         d3 = CustomData_bmesh_get_n(&bm->edata, e1->head.data, CD_PROP_FLT, li);
1956                                         d1 = *(float *)CustomData_bmesh_get_n(&bm->edata, l->prev->e->head.data, CD_PROP_FLT, li);
1957                                         d2 = *(float *)CustomData_bmesh_get_n(&bm->edata, l2->e->head.data, CD_PROP_FLT, li);
1958 #if 0
1959                                         ang = angle_v3v3v3(l->prev->v->co, l->v->co, BM_edge_other_vert(l2->e, l->v)->co);
1960 #endif
1961                                         *d3 = (d1 + d2) * 0.5f;
1962                                         
1963                                         d3 = CustomData_bmesh_get_n(&bm->edata, e2->head.data, CD_PROP_FLT, li);
1964                                         d1 = *(float *)CustomData_bmesh_get_n(&bm->edata, l->next->e->head.data, CD_PROP_FLT, li);
1965                                         d2 = *(float *)CustomData_bmesh_get_n(&bm->edata, l3->e->head.data, CD_PROP_FLT, li);
1966 #if 0
1967                                         ang = angle_v3v3v3(BM_edge_other_vert(l->next->e, l->next->v)->co, l->next->v->co,
1968                                                            BM_edge_other_vert(l3->e, l->next->v)->co);
1969 #endif
1970                                         *d3 = (d1 + d2) * 0.5f;
1971                                 }
1972
1973                                 if (UNLIKELY(f == NULL)) {
1974                                         fprintf(stderr, "%s: face index out of range! (bmesh internal error)\n", __func__);
1975                                         continue;
1976                                 }
1977                                 
1978                                 BMO_elem_flag_enable(bm, f, FACE_NEW | FACE_SPAN);
1979                                 
1980                                 /* un-tag edges in f for deletio */
1981                                 BM_ITER_ELEM (l2, &liter2, f, BM_LOOPS_OF_FACE) {
1982                                         BMO_elem_flag_disable(bm, l2->e, BEVEL_DEL);
1983                                 }
1984                         }
1985                         else {
1986                                 f = NULL;
1987                         }
1988                 }
1989         }
1990         
1991         /* fill in holes at vertices */
1992         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
1993                 BMIter eiter;
1994                 BMVert *vv, *vstart = NULL, *lastv = NULL;
1995                 SmallHash tmphash;
1996                 int rad, insorig = 0, err = 0;
1997
1998                 BLI_smallhash_init(&tmphash);
1999
2000                 if (!BMO_elem_flag_test(bm, v, BEVEL_FLAG))
2001                         continue;
2002                 
2003                 BLI_array_empty(verts);
2004                 BLI_array_empty(edges);
2005                 
2006                 BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
2007                         BMIter liter;
2008                         BMVert *v1 = NULL, *v2 = NULL;
2009                         BMLoop *l;
2010                         
2011                         if (BM_edge_face_count(e) < 2)
2012                                 insorig = 1;
2013                         
2014                         if (BM_elem_index_get(e) == -1)
2015                                 continue;
2016                         
2017                         rad = 0;
2018                         BM_ITER_ELEM (l, &liter, e, BM_LOOPS_OF_EDGE) {
2019                                 if (!BMO_elem_flag_test(bm, l->f, FACE_OLD))
2020                                         continue;
2021                                 
2022                                 rad++;
2023                                 
2024                                 tag = tags + BM_elem_index_get((l->v == v) ? l : l->next);
2025                                 
2026                                 if (!v1)
2027                                         v1 = tag->newv;
2028                                 else if (!v2)
2029                                         v2 = tag->newv;
2030                         }
2031                         
2032                         if (rad < 2)
2033                                 insorig = 1;
2034                         
2035                         if (!v1)
2036                                 v1 = ETAG_GET(e, v);
2037                         if (!v2 || v1 == v2)
2038                                 v2 = ETAG_GET(e, v);
2039                         
2040                         if (v1) {
2041                                 if (!BLI_smallhash_haskey(&tmphash, (intptr_t)v1)) {
2042                                         BLI_array_append(verts, v1);
2043                                         BLI_smallhash_insert(&tmphash, (intptr_t)v1, NULL);
2044                                 }
2045                                 
2046                                 if (v2 && v1 != v2 && !BLI_smallhash_haskey(&tmphash, (intptr_t)v2)) {
2047                                         BLI_array_append(verts, v2);
2048                                         BLI_smallhash_insert(&tmphash, (intptr_t)v2, NULL);
2049                                 }
2050                         }
2051                 }
2052                 
2053                 if (!BLI_array_count(verts))
2054                         continue;
2055                 
2056                 if (insorig) {
2057                         BLI_array_append(verts, v);
2058                         BLI_smallhash_insert(&tmphash, (intptr_t)v, NULL);
2059                 }
2060                 
2061                 /* find edges that exist between vertices in verts.  this is basically
2062                  * a topological walk of the edges connecting them */
2063                 vstart = vstart ? vstart : verts[0];
2064                 vv = vstart;
2065                 do {
2066                         BM_ITER_ELEM (e, &eiter, vv, BM_EDGES_OF_VERT) {
2067                                 BMVert *vv2 = BM_edge_other_vert(e, vv);
2068                                 
2069                                 if (vv2 != lastv && BLI_smallhash_haskey(&tmphash, (intptr_t)vv2)) {
2070                                         /* if we've go over the same vert twice, break out of outer loop */
2071                                         if (BLI_smallhash_lookup(&tmphash, (intptr_t)vv2) != NULL) {
2072                                                 e = NULL;
2073                                                 err = 1;
2074                                                 break;
2075                                         }
2076                                         
2077                                         /* use self pointer as ta */
2078                                         BLI_smallhash_remove(&tmphash, (intptr_t)vv2);
2079                                         BLI_smallhash_insert(&tmphash, (intptr_t)vv2, vv2);
2080                                         
2081                                         lastv = vv;
2082                                         BLI_array_append(edges, e);
2083                                         vv = vv2;
2084                                         break;
2085                                 }
2086                         }
2087
2088                         if (e == NULL) {
2089                                 break;
2090                         }
2091                 } while (vv != vstart);
2092                 
2093                 if (err) {
2094                         continue;
2095                 }
2096
2097                 /* there may not be a complete loop of edges, so start again and make
2098                  * final edge afterwards.  in this case, the previous loop worked to
2099                  * find one of the two edges at the extremes. */
2100                 if (vv != vstart) {
2101                         /* undo previous taggin */
2102                         for (i = 0; i < BLI_array_count(verts); i++) {
2103                                 BLI_smallhash_remove(&tmphash, (intptr_t)verts[i]);
2104                                 BLI_smallhash_insert(&tmphash, (intptr_t)verts[i], NULL);
2105                         }
2106
2107                         vstart = vv;
2108                         lastv = NULL;
2109                         BLI_array_empty(edges);
2110                         do {
2111                                 BM_ITER_ELEM (e, &eiter, vv, BM_EDGES_OF_VERT) {
2112                                         BMVert *vv2 = BM_edge_other_vert(e, vv);
2113                                         
2114                                         if (vv2 != lastv && BLI_smallhash_haskey(&tmphash, (intptr_t)vv2)) {
2115                                                 /* if we've go over the same vert twice, break out of outer loo */
2116                                                 if (BLI_smallhash_lookup(&tmphash, (intptr_t)vv2) != NULL) {
2117                                                         e = NULL;
2118                                                         err = 1;
2119                                                         break;
2120                                                 }
2121                                                 
2122                                                 /* use self pointer as ta */
2123                                                 BLI_smallhash_remove(&tmphash, (intptr_t)vv2);
2124                                                 BLI_smallhash_insert(&tmphash, (intptr_t)vv2, vv2);
2125                                                 
2126                                                 lastv = vv;
2127                                                 BLI_array_append(edges, e);
2128                                                 vv = vv2;
2129                                                 break;
2130                                         }
2131                                 }
2132                                 if (e == NULL)
2133                                         break;
2134                         } while (vv != vstart);
2135                         
2136                         if (!err) {
2137                                 e = BM_edge_create(bm, vv, vstart, NULL, TRUE);
2138                                 BLI_array_append(edges, e);
2139                         }
2140                 }
2141                 
2142                 if (err)
2143                         continue;
2144                 
2145                 if (BLI_array_count(edges) >= 3) {
2146                         BMFace *f;
2147                         
2148                         if (BM_face_exists(bm, verts, BLI_array_count(verts), &f))
2149                                 continue;
2150                         
2151                         f = BM_face_create_ngon(bm, lastv, vstart, edges, BLI_array_count(edges), FALSE);
2152                         if (UNLIKELY(f == NULL)) {
2153                                 fprintf(stderr, "%s: in bevel vert fill! (bmesh internal error)\n", __func__);
2154                         }
2155                         else {
2156                                 BMO_elem_flag_enable(bm, f, FACE_NEW | FACE_HOLE);
2157                         }
2158                 }
2159                 BLI_smallhash_release(&tmphash);
2160         }
2161         
2162         /* copy over customdat */
2163         for (i = 0; i < BLI_array_count(faces); i++) {
2164                 BMLoop *l;
2165                 BMIter liter;
2166                 BMFace *f = faces[i];
2167                 
2168                 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
2169                         BMLoop *l2;
2170                         BMIter liter2;
2171                         
2172                         tag = tags + BM_elem_index_get(l);
2173                         if (!tag->newv)
2174                                 continue;
2175                         
2176                         BM_ITER_ELEM (l2, &liter2, tag->newv, BM_LOOPS_OF_VERT) {
2177                                 if (!BMO_elem_flag_test(bm, l2->f, FACE_NEW) || (l2->v != tag->newv && l2->v != l->v))
2178                                         continue;
2179                                 
2180                                 if (tag->newv != l->v || HasMDisps) {
2181                                         BM_elem_attrs_copy(bm, bm, l->f, l2->f);
2182                                         BM_loop_interp_from_face(bm, l2, l->f, TRUE, TRUE);
2183                                 }
2184                                 else {
2185                                         BM_elem_attrs_copy(bm, bm, l->f, l2->f);
2186                                         BM_elem_attrs_copy(bm, bm, l, l2);
2187                                 }
2188                                 
2189                                 if (HasMDisps) {
2190                                         BMLoop *l3;
2191                                         BMIter liter3;
2192                                         
2193                                         BM_ITER_ELEM (l3, &liter3, l2->f, BM_LOOPS_OF_FACE) {
2194                                                 BM_loop_interp_multires(bm, l3, l->f);
2195                                         }
2196                                 }
2197                         }
2198                 }
2199         }
2200         
2201         /* handle vertices along boundary edge */
2202         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
2203                 if (BMO_elem_flag_test(bm, v, VERT_OLD) &&
2204                     BMO_elem_flag_test(bm, v, BEVEL_FLAG) &&
2205                     !BMO_elem_flag_test(bm, v, BEVEL_DEL))
2206                 {
2207                         BMLoop *l;
2208                         BMLoop *lorig = NULL;
2209                         BMIter liter;
2210                         
2211                         BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
2212                                 // BMIter liter2;
2213                                 // BMLoop *l2 = l->v == v ? l : l->next, *l3;
2214                                 
2215                                 if (BMO_elem_flag_test(bm, l->f, FACE_OLD)) {
2216                                         lorig = l;
2217                                         break;
2218                                 }
2219                         }
2220                         
2221                         if (!lorig)
2222                                 continue;
2223                         
2224                         BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
2225                                 BMLoop *l2 = l->v == v ? l : l->next;
2226                                 
2227                                 BM_elem_attrs_copy(bm, bm, lorig->f, l2->f);
2228                                 BM_elem_attrs_copy(bm, bm, lorig, l2);
2229                         }
2230                 }
2231         }
2232 #if 0
2233         /* clean up any remaining 2-edged face */
2234         BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
2235                 if (f->len == 2) {
2236                         BMFace *faces[2] = {f, BM_FACE_FIRST_LOOP(f)->radial_next->f};
2237                         
2238                         if (faces[0] == faces[1])
2239                                 BM_face_kill(bm, f);
2240                         else
2241                                 BM_faces_join(bm, faces, 2);
2242                 }
2243         }
2244 #endif
2245
2246         BMO_op_callf(bm, op->flag, "delete geom=%fv context=%i", BEVEL_DEL, DEL_VERTS);
2247
2248         /* clean up any edges that might not get properly delete */
2249         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
2250                 if (BMO_elem_flag_test(bm, e, EDGE_OLD) && !e->l)
2251                         BMO_elem_flag_enable(bm, e, BEVEL_DEL);
2252         }
2253
2254         BMO_op_callf(bm, op->flag, "delete geom=%fe context=%i", BEVEL_DEL, DEL_EDGES);
2255         BMO_op_callf(bm, op->flag, "delete geom=%ff context=%i", BEVEL_DEL, DEL_FACES);
2256         
2257         BLI_smallhash_release(&hash);
2258         BLI_array_free(tags);
2259         BLI_array_free(etags);
2260         BLI_array_free(verts);
2261         BLI_array_free(edges);
2262         BLI_array_free(faces);
2263         
2264         BMO_slot_buffer_from_enabled_flag(bm, op, "face_spans", BM_FACE, FACE_SPAN);
2265         BMO_slot_buffer_from_enabled_flag(bm, op, "face_holes", BM_FACE, FACE_HOLE);
2266 }
2267 #endif  /* NEW_BEVEL */