add option not to delete edges/verts when joining faces, needed so we can loop over...
[blender-staging.git] / source / blender / bmesh / tools / BME_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  * The Original Code is Copyright (C) 2004 Blender Foundation.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): Geoffrey Bantle and Levi Schooley.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 #include <math.h>
29
30 #include "MEM_guardedalloc.h"
31
32 #include "DNA_listBase.h"
33 #include "DNA_meshdata_types.h"
34 #include "DNA_mesh_types.h"
35
36 #include "BLI_math.h"
37 #include "BLI_blenlib.h"
38 #include "BLI_ghash.h"
39 #include "BLI_memarena.h"
40
41 #include "BKE_utildefines.h"
42 #include "BKE_tessmesh.h"
43 #include "BKE_bmesh.h"
44
45 #include "bmesh.h"
46 #include "intern/bmesh_private.h"
47
48 /* BMESH_TODO
49  *
50  * Date: 2011-11-24 06:25
51  * Sender: Andrew Wiggin
52  * Status update: I have code changes to actually make basic bevel modifier work. The things that still need to be done:
53  * - clean up the changes
54  * - get bevel by weight and bevel by angles working
55  * - the code uses adaptations of a couple of bmesh APIs,
56  * that work a little differently. for example, a join faces that doesn't just create a new face and then delete the
57  * original two faces and all associated loops, it extends one of the original faces to cover all the original loops
58  * (except for the loop on the join edge which is of course deleted). the bevel code currently requires this because it
59  * expects to be able to continue walking loop lists and doesn't like for loops to be deleted out from under it
60  * while working...
61  * but bmesh APIs don't do it this way because it makes it trickier to manage the interp during these operations,
62  * so I need to decide what to do in these cases.
63  */
64
65 /* ------- Bevel code starts here -------- */
66
67 BME_TransData_Head *BME_init_transdata(int bufsize)
68 {
69         BME_TransData_Head *td;
70
71         td = MEM_callocN(sizeof(BME_TransData_Head), "BM transdata header");
72         td->gh = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "BME_init_transdata gh");
73         td->ma = BLI_memarena_new(bufsize, "BME_TransData arena");
74         BLI_memarena_use_calloc(td->ma);
75
76         return td;
77 }
78
79 void BME_free_transdata(BME_TransData_Head *td)
80 {
81         BLI_ghash_free(td->gh, NULL, NULL);
82         BLI_memarena_free(td->ma);
83         MEM_freeN(td);
84 }
85
86 BME_TransData *BME_assign_transdata(
87         BME_TransData_Head *td, BMesh *bm, BMVert *v,
88         float *co, float *org, float *vec, float *loc,
89         float factor, float weight, float maxfactor, float *max)
90 {
91         BME_TransData *vtd;
92         int is_new = 0;
93
94         if (v == NULL) {
95                 return NULL;
96         }
97
98         if ((vtd = BLI_ghash_lookup(td->gh, v)) == NULL && bm != NULL) {
99                 vtd = BLI_memarena_alloc(td->ma, sizeof(*vtd));
100                 BLI_ghash_insert(td->gh, v, vtd);
101                 td->len++;
102                 is_new = 1;
103         }
104
105         vtd->bm = bm;
106         vtd->v = v;
107
108         if (co != NULL) {
109                 copy_v3_v3(vtd->co, co);
110         }
111
112         if (org == NULL && is_new) {
113                 copy_v3_v3(vtd->org, v->co); /* default */
114         }
115         else if (org != NULL) {
116                 copy_v3_v3(vtd->org, org);
117         }
118
119         if (vec != NULL) {
120                 copy_v3_v3(vtd->vec, vec);
121                 normalize_v3(vtd->vec);
122         }
123
124         vtd->loc = loc;
125
126         vtd->factor = factor;
127         vtd->weight = weight;
128         vtd->maxfactor = maxfactor;
129         vtd->max = max;
130
131         return vtd;
132 }
133
134 BME_TransData *BME_get_transdata(BME_TransData_Head *td, BMVert *v)
135 {
136         BME_TransData *vtd;
137         vtd = BLI_ghash_lookup(td->gh, v);
138         return vtd;
139 }
140
141 /* a hack (?) to use the transdata memarena to allocate floats for use with the max limits */
142 float *BME_new_transdata_float(BME_TransData_Head *td)
143 {
144         return BLI_memarena_alloc(td->ma, sizeof(float));
145 }
146
147 /* BM_disk_dissolve is a real mess, and crashes bevel if called instead of this.
148  * The drawback, though, is that this code doesn't merge customdata. */
149 static int BME_Bevel_Dissolve_Disk(BMesh *bm, BMVert *v)
150 {
151         BMIter iter;
152         BMEdge *e, *elast;
153         BMLoop *l1, *l2;
154
155         if (!BM_vert_is_manifold(v)) {
156                 return 0;
157         }
158
159         BM_ITER(e, &iter, bm, BM_EDGES_OF_VERT, v) {
160                 if (BM_edge_face_count(e) != 2) {
161                         return 0;
162                 }
163         }
164
165         if (BM_vert_edge_count(v) > 2) {
166                 while (BM_vert_edge_count(v) > 2) {
167                         e = v->e;
168                         l1 = e->l;
169                         l2 = l1->radial_next;
170                         if (l1->v == l2->v) {
171                                 /* faces have incompatible directions; need to reverse one */
172                                 if (!bmesh_loop_reverse(bm, l2->f)) {
173                                         BLI_assert(!"bevel dissolve disk cannot reverse loop");
174                                         return 0;
175                                 }
176                                 l2 = l1->radial_next;
177                         }
178                         if (!bmesh_jfke(bm, l1->f, l2->f, e)) {
179                                 BLI_assert(!"bevel dissolve disk cannot join faces");
180                                 return 0;
181                         }
182                 }
183
184                 e = v->e;
185                 elast = bmesh_disk_edge_next(e, v);
186
187                 /* BMESH_TODO, figure out if its possible we had a double edge here and need to splice it,
188                  * last bool arg */
189                 bmesh_jekv(bm, e, v, FALSE);
190
191                 l1 = elast->l;
192                 l2 = l1->radial_next;
193                 if (l1->v == l2->v) {
194                         /* faces have incompatible directions */
195                                 if (!bmesh_loop_reverse(bm, l2->f)) {
196                                         BLI_assert(!"bevel dissolve disk cannot reverse loop");
197                                         return 0;
198                                 }
199                                 l2 = l1->radial_next;
200                 }
201                 bmesh_jfke(bm, l1->f, l2->f, elast);
202         }
203
204         return 1;
205 }
206
207 static int BME_bevel_is_split_vert(BMesh *bm, BMLoop *l)
208 {
209         /* look for verts that have already been added to the edge when
210          * beveling other polys; this can be determined by testing the
211          * vert and the edges around it for originality
212          */
213         if (!BMO_elem_flag_test(bm, l->v, BME_BEVEL_ORIG) &&
214              BMO_elem_flag_test(bm, l->e, BME_BEVEL_ORIG) &&
215              BMO_elem_flag_test(bm, l->prev->e, BME_BEVEL_ORIG))
216         {
217                 return 1;
218         }
219         return 0;
220 }
221
222 /* get a vector, vec, that points from v1->co to wherever makes sense to
223  * the bevel operation as a whole based on the relationship between v1 and v2
224  * (won't necessarily be a vec from v1->co to v2->co, though it probably will be);
225  * the return value is -1 for failure, 0 if we used vert co's, and 1 if we used transform origins */
226 static int BME_bevel_get_vec(float *vec, BMVert *v1, BMVert *v2, BME_TransData_Head *td)
227 {
228         BME_TransData *vtd1, *vtd2;
229
230         vtd1 = BME_get_transdata(td, v1);
231         vtd2 = BME_get_transdata(td, v2);
232         if (!vtd1 || !vtd2) {
233                 //printf("BME_bevel_get_vec() got called without proper BME_TransData\n");
234                 return -1;
235         }
236
237         /* compare the transform origins to see if we can use the vert co's;
238          * if they belong to different origins, then we will use the origins to determine
239          * the vector */
240         if (compare_v3v3(vtd1->org, vtd2->org, 0.000001f)) {
241                 sub_v3_v3v3(vec, v2->co, v1->co);
242                 if (len_v3(vec) < 0.000001f) {
243                         zero_v3(vec);
244                 }
245                 return 0;
246         }
247         else {
248                 sub_v3_v3v3(vec, vtd2->org, vtd1->org);
249                 if (len_v3(vec) < 0.000001f) {
250                         zero_v3(vec);
251                 }
252                 return 1;
253         }
254 }
255
256 /* "Projects" a vector perpendicular to vec2 against vec1, such that
257  * the projected vec1 + vec2 has a min distance of 1 from the "edge" defined by vec2.
258  * note: the direction, is_forward, is used in conjunction with up_vec to determine
259  * whether this is a convex or concave corner. If it is a concave corner, it will
260  * be projected "backwards." If vec1 is before vec2, is_forward should be 0 (we are projecting backwards).
261  * vec1 is the vector to project onto (expected to be normalized)
262  * vec2 is the direction of projection (pointing away from vec1)
263  * up_vec is used for orientation (expected to be normalized)
264  * returns the length of the projected vector that lies along vec1 */
265 static float BME_bevel_project_vec(float *vec1, float *vec2, float *up_vec, int is_forward, BME_TransData_Head *UNUSED(td))
266 {
267         float factor, vec3[3], tmp[3], c1, c2;
268
269         cross_v3_v3v3(tmp, vec1, vec2);
270         normalize_v3(tmp);
271         factor = dot_v3v3(up_vec, tmp);
272         if ((factor > 0 && is_forward) || (factor < 0 && !is_forward)) {
273                 cross_v3_v3v3(vec3, vec2, tmp); /* hmm, maybe up_vec should be used instead of tmp */
274         }
275         else {
276                 cross_v3_v3v3(vec3, tmp, vec2); /* hmm, maybe up_vec should be used instead of tmp */
277         }
278         normalize_v3(vec3);
279         c1 = dot_v3v3(vec3, vec1);
280         c2 = dot_v3v3(vec1, vec1);
281         if (fabsf(c1) < 0.000001f || fabsf(c2) < 0.000001f) {
282                 factor = 0.0f;
283         }
284         else {
285                 factor = c2 / c1;
286         }
287
288         return factor;
289 }
290
291 /* BME_bevel_split_edge() is the main math work-house; its responsibilities are:
292  * using the vert and the loop passed, get or make the split vert, set its coordinates
293  * and transform properties, and set the max limits.
294  * Finally, return the split vert. */
295 static BMVert *BME_bevel_split_edge(BMesh *bm, BMVert *v, BMVert *v1, BMLoop *l, float *up_vec, float value, BME_TransData_Head *td)
296 {
297         BME_TransData *vtd, *vtd1, *vtd2;
298         BMVert *sv, *v2, *v3, *ov;
299         BMLoop *lv1, *lv2;
300         BMEdge *ne, *e1, *e2;
301         float maxfactor, scale, len, dis, vec1[3], vec2[3], t_up_vec[3];
302         int is_edge, forward, is_split_vert;
303
304         /* ov, vtd2, and is_split_vert are set but UNUSED */
305         (void)ov, (void)vtd2, (void)is_split_vert;
306
307         if (l == NULL) {
308                 /* what you call operator overloading in C :)
309                  * I wanted to use the same function for both wire edges and poly loops
310                  * so... here we walk around edges to find the needed verts */
311                 forward = 1;
312                 is_split_vert = 0;
313                 if (v->e == NULL) {
314                         //printf("We can't split a loose vert's edge!\n");
315                         return NULL;
316                 }
317                 e1 = v->e; /* we just use the first two edges */
318                 e2 = bmesh_disk_edge_next(v->e, v);
319                 if (e1 == e2) {
320                         //printf("You need at least two edges to use BME_bevel_split_edge()\n");
321                         return NULL;
322                 }
323                 v2 = BM_edge_other_vert(e1, v);
324                 v3 = BM_edge_other_vert(e2, v);
325                 if (v1 != v2 && v1 != v3) {
326                         //printf("Error: more than 2 edges in v's disk cycle, or v1 does not share an edge with v\n");
327                         return NULL;
328                 }
329                 if (v1 == v2) {
330                         v2 = v3;
331                 }
332                 else {
333                         e1 = e2;
334                 }
335                 ov = BM_edge_other_vert(e1, v);
336                 sv = BM_edge_split(bm, e1, v, &ne, 0);
337                 //BME_data_interp_from_verts(bm, v, ov, sv, 0.25); /* this is technically wrong.. */
338                 //BME_data_interp_from_faceverts(bm, v, ov, sv, 0.25);
339                 //BME_data_interp_from_faceverts(bm, ov, v, sv, 0.25);
340                 BME_assign_transdata(td, bm, sv, sv->co, sv->co, NULL, sv->co, 0, -1, -1, NULL); /* quick default */
341                 BMO_elem_flag_enable(bm, sv, BME_BEVEL_BEVEL);
342                 BMO_elem_flag_enable(bm, ne, BME_BEVEL_ORIG); /* mark edge as original, even though it isn't */
343                 BME_bevel_get_vec(vec1, v1, v, td);
344                 BME_bevel_get_vec(vec2, v2, v, td);
345                 cross_v3_v3v3(t_up_vec, vec1, vec2);
346                 normalize_v3(t_up_vec);
347                 up_vec = t_up_vec;
348         }
349         else {
350                 /* establish loop direction */
351                 if (l->v == v) {
352                         forward = 1;
353                         lv1 = l->next;
354                         lv2 = l->prev;
355                         v1 = l->next->v;
356                         v2 = l->prev->v;
357                 }
358                 else if (l->next->v == v) {
359                         forward = 0;
360                         lv1 = l;
361                         lv2 = l->next->next;
362                         v1 = l->v;
363                         v2 = l->next->next->v;
364                 }
365                 else {
366                         //printf("ERROR: BME_bevel_split_edge() - v must be adjacent to l\n");
367                         return NULL;
368                 }
369
370                 if (BME_bevel_is_split_vert(bm, lv1)) {
371                         is_split_vert = 1;
372                         sv = v1;
373                         v1 = forward ? l->next->next->v : l->prev->v;
374                 }
375                 else {
376                         is_split_vert = 0;
377                         ov = BM_edge_other_vert(l->e, v);
378                         sv = BM_edge_split(bm, l->e, v, &ne, 0);
379                         //BME_data_interp_from_verts(bm, v, ov, sv, 0.25); /* this is technically wrong.. */
380                         //BME_data_interp_from_faceverts(bm, v, ov, sv, 0.25);
381                         //BME_data_interp_from_faceverts(bm, ov, v, sv, 0.25);
382                         BME_assign_transdata(td, bm, sv, sv->co, sv->co, NULL, sv->co, 0, -1, -1, NULL); /* quick default */
383                         BMO_elem_flag_enable(bm, sv, BME_BEVEL_BEVEL);
384                         BMO_elem_flag_enable(bm, ne, BME_BEVEL_ORIG); /* mark edge as original, even though it isn't */
385                 }
386
387                 if (BME_bevel_is_split_vert(bm, lv2)) {
388                         v2 = forward ? lv2->prev->v : lv2->next->v;
389                 }
390         }
391
392         is_edge = BME_bevel_get_vec(vec1, v, v1, td); /* get the vector we will be projecting onto */
393         BME_bevel_get_vec(vec2, v, v2, td); /* get the vector we will be projecting parallel to */
394         len = len_v3(vec1);
395         normalize_v3(vec1);
396
397         vtd = BME_get_transdata(td, sv);
398         vtd1 = BME_get_transdata(td, v);
399         vtd2 = BME_get_transdata(td, v1);
400
401         if (vtd1->loc == NULL) {
402                 /* this is a vert with data only for calculating initial weights */
403                 if (vtd1->weight < 0) {
404                         vtd1->weight = 0;
405                 }
406                 scale = vtd1->weight / vtd1->factor;
407                 if (!vtd1->max) {
408                         vtd1->max = BME_new_transdata_float(td);
409                         *vtd1->max = -1;
410                 }
411         }
412         else {
413                 scale = vtd1->weight;
414         }
415         vtd->max = vtd1->max;
416
417         if (is_edge && vtd1->loc != NULL) {
418                 maxfactor = vtd1->maxfactor;
419         }
420         else {
421                 maxfactor = scale * BME_bevel_project_vec(vec1, vec2, up_vec, forward, td);
422                 if (vtd->maxfactor > 0 && vtd->maxfactor < maxfactor) {
423                         maxfactor = vtd->maxfactor;
424                 }
425         }
426
427         dis = BMO_elem_flag_test(bm, v1, BME_BEVEL_ORIG) ? len / 3 : len / 2;
428         if (is_edge || dis > maxfactor * value) {
429                 dis = maxfactor * value;
430         }
431         madd_v3_v3v3fl(sv->co, v->co, vec1, dis);
432         sub_v3_v3v3(vec1, sv->co, vtd1->org);
433         dis = len_v3(vec1);
434         normalize_v3(vec1);
435         BME_assign_transdata(td, bm, sv, vtd1->org, vtd1->org, vec1, sv->co, dis, scale, maxfactor, vtd->max);
436
437         return sv;
438 }
439
440 #if 0 /* UNUSED */
441 static float BME_bevel_set_max(BMVert *v1, BMVert *v2, float value, BME_TransData_Head *td)
442 {
443         BME_TransData *vtd1, *vtd2;
444         float max, fac1, fac2, vec1[3], vec2[3], vec3[3];
445
446         BME_bevel_get_vec(vec1, v1, v2, td);
447         vtd1 = BME_get_transdata(td, v1);
448         vtd2 = BME_get_transdata(td, v2);
449
450         if (vtd1->loc == NULL) {
451                 fac1 = 0;
452         }
453         else {
454                 copy_v3_v3(vec2, vtd1->vec);
455                 mul_v3_fl(vec2, vtd1->factor);
456                 if (dot_v3v3(vec1, vec1)) {
457                         project_v3_v3v3(vec2, vec2, vec1);
458                         fac1 = len_v3(vec2) / value;
459                 }
460                 else {
461                         fac1 = 0;
462                 }
463         }
464
465         if (vtd2->loc == NULL) {
466                 fac2 = 0;
467         }
468         else {
469                 copy_v3_v3(vec3, vtd2->vec);
470                 mul_v3_fl(vec3, vtd2->factor);
471                 if (dot_v3v3(vec1, vec1)) {
472                         project_v3_v3v3(vec2, vec3, vec1);
473                         fac2 = len_v3(vec2) / value;
474                 }
475                 else {
476                         fac2 = 0;
477                 }
478         }
479
480         if (fac1 || fac2) {
481                 max = len_v3(vec1) / (fac1 + fac2);
482                 if (vtd1->max && (*vtd1->max < 0 || max < *vtd1->max)) {
483                         *vtd1->max = max;
484                 }
485                 if (vtd2->max && (*vtd2->max < 0 || max < *vtd2->max)) {
486                         *vtd2->max = max;
487                 }
488         }
489         else {
490                 max = -1;
491         }
492
493         return max;
494 }
495 #endif
496
497 #if 0 /* UNUSED */
498 static BMVert *BME_bevel_wire(BMesh *bm, BMVert *v, float value, int res, int UNUSED(options), BME_TransData_Head *td)
499 {
500         BMVert *ov1, *ov2, *v1, *v2;
501
502         ov1 = BM_edge_other_vert(v->e, v);
503         ov2 = BM_edge_other_vert(bmesh_disk_edge_next(v->e, v), v);
504
505         /* split the edges */
506         v1 = BME_bevel_split_edge(bm, v, ov1, NULL, NULL, value, td);
507         BMO_elem_flag_enable(bm, v1, BME_BEVEL_NONMAN);
508         v2 = BME_bevel_split_edge(bm, v, ov2, NULL, NULL, value, td);
509         BMO_elem_flag_enable(bm, v2, BME_BEVEL_NONMAN);
510
511         if (value > 0.5) {
512                 BME_bevel_set_max(v1, ov1, value, td);
513                 BME_bevel_set_max(v2, ov2, value, td);
514         }
515
516         /* remove the original vert */
517         if (res) {
518                 /* bmesh_jekv; */
519
520                 //void BM_vert_collapse_faces(BMesh *bm, BMEdge *ke, BMVert *kv, float fac, int calcnorm) {
521                 //hrm, why is there a fac here? it just removes a vert
522                 BM_vert_collapse_edge(bm, v->e, v);
523         }
524
525         return v1;
526 }
527 #endif
528
529 static BMLoop *BME_bevel_edge(BMesh *bm, BMLoop *l, float value, int UNUSED(options), float *up_vec, BME_TransData_Head *td)
530 {
531         BMVert *v1, *v2, *kv;
532         BMLoop *kl = NULL, *nl;
533         BMEdge *e, *ke, *se;
534         BMFace *f, *jf;
535
536         f = l->f;
537         e = l->e;
538
539         /* sanity check */
540         if (!BMO_elem_flag_test(bm, l->e, BME_BEVEL_BEVEL) &&
541             (BMO_elem_flag_test(bm, l->v, BME_BEVEL_BEVEL) || BMO_elem_flag_test(bm, l->next->v, BME_BEVEL_BEVEL)))
542         {
543                 return l;
544         }
545
546         /* checks and operations for prev edge */
547         /* first, check to see if this edge was inset previously */
548         if (!BMO_elem_flag_test(bm, l->prev->e, BME_BEVEL_ORIG) &&
549             !BMO_elem_flag_test(bm, l->v, BME_BEVEL_NONMAN))
550         {
551                 kl = l->prev->radial_next;
552                 kl = (kl->v == l->v) ? kl->prev : kl->next;
553                 kv = l->v;
554         }
555         else {
556                 kv = NULL;
557         }
558         /* get/make the first vert to be used in SFME */
559         if (BMO_elem_flag_test(bm, l->v, BME_BEVEL_NONMAN)) {
560                 v1 = l->v;
561         }
562         else { /* we'll need to split the previous edge */
563                 v1 = BME_bevel_split_edge(bm, l->v, NULL, l->prev, up_vec, value, td);
564         }
565         /* if we need to clean up geometry... */
566         if (kv) {
567                 se = l->next->e;
568                 jf = NULL;
569                 if (kl->v == kv) {
570                         BM_face_split(bm, kl->f, kl->prev->v, kl->next->v, &nl, kl->prev->e, FALSE);
571                         ke = kl->e;
572                         /* BMESH-TODO: jfke doesn't handle customdata */
573                         jf = bmesh_jfke(bm, kl->prev->radial_next->f, kl->f, kl->prev->e);
574                         BM_vert_collapse_edge(bm, ke, kv, FALSE);
575                 }
576                 else {
577                         BM_face_split(bm, kl->f, kl->next->next->v, kl->v, &nl, kl->next->e, FALSE);
578                         ke = kl->e;
579                         /* BMESH-TODO: jfke doesn't handle customdata */
580                         jf = bmesh_jfke(bm, kl->next->radial_next->f, kl->f, kl->next->e);
581                         BM_vert_collapse_edge(bm, ke, kv, FALSE);
582                 }
583                 /* find saved loop pointer */
584                 l = se->l;
585                 while (l->f != jf) {
586                         l = l->radial_next;
587                         BLI_assert(l != se->l);
588                 }
589                 l = l->prev;
590         }
591
592         /* checks and operations for the next edge */
593         /* first, check to see if this edge was inset previously  */
594         if (!BMO_elem_flag_test(bm, l->next->e, BME_BEVEL_ORIG) &&
595             !BMO_elem_flag_test(bm, l->next->v, BME_BEVEL_NONMAN))
596         {
597                 kl = l->next->radial_next;
598                 kl = (kl->v == l->next->v) ? kl->prev : kl->next;
599                 kv = l->next->v;
600         }
601         else {
602                 kv = NULL;
603         }
604         /* get/make the second vert to be used in SFME */
605         if (BMO_elem_flag_test(bm, l->next->v, BME_BEVEL_NONMAN)) {
606                 v2 = l->next->v;
607         }
608         else { /* we'll need to split the next edge */
609                 v2 = BME_bevel_split_edge(bm, l->next->v, NULL, l->next, up_vec, value, td);
610         }
611         /* if we need to clean up geometry... */
612         if (kv) {
613                 se = l->e;
614                 jf = NULL;
615                 if (kl->v == kv) {
616                         BM_face_split(bm, kl->f, kl->prev->v, kl->next->v, &nl, kl->prev->e, FALSE);
617                         ke = kl->e;
618                         /* BMESH-TODO: jfke doesn't handle customdata */
619                         jf = bmesh_jfke(bm, kl->prev->radial_next->f, kl->f, kl->prev->e);
620                         BM_vert_collapse_edge(bm, ke, kv, FALSE);
621                 }
622                 else {
623                         BM_face_split(bm, kl->f, kl->next->next->v, kl->v, &nl, kl->next->e, FALSE);
624                         ke = kl->e;
625                         /* BMESH-TODO: jfke doesn't handle customdata */
626                         jf = bmesh_jfke(bm, kl->next->radial_next->f, kl->f, kl->next->e);
627                         BM_vert_collapse_edge(bm, ke, kv, FALSE);
628                 }
629                 /* find saved loop pointer */
630                 l = se->l;
631                 while (l->f != jf) {
632                         l = l->radial_next;
633                         BLI_assert(l != se->l);
634                 }
635         }
636
637         if (!BMO_elem_flag_test(bm, v1, BME_BEVEL_NONMAN) || !BMO_elem_flag_test(bm, v2, BME_BEVEL_NONMAN)) {
638                 BM_face_split(bm, f, v2, v1, &l, e, FALSE);
639                 BMO_elem_flag_enable(bm, l->e, BME_BEVEL_BEVEL);
640                 l = l->radial_next;
641         }
642
643         if (l->f != f) {
644                 //printf("Whoops! You got something out of order in BME_bevel_edge()!\n");
645         }
646
647         return l;
648 }
649
650 static BMLoop *BME_bevel_vert(BMesh *bm, BMLoop *l, float value, int UNUSED(options), float *up_vec, BME_TransData_Head *td)
651 {
652         BMVert *v1, *v2;
653         /* BMFace *f; */ /* UNUSED */
654
655         /* get/make the first vert to be used in SFME */
656         /* may need to split the previous edge */
657         v1 = BME_bevel_split_edge(bm, l->v, NULL, l->prev, up_vec, value, td);
658
659         /* get/make the second vert to be used in SFME */
660         /* may need to split this edge (so move l) */
661         l = l->prev;
662         v2 = BME_bevel_split_edge(bm, l->next->v, NULL, l->next, up_vec, value, td);
663         l = l->next->next;
664
665         /* "cut off" this corner */
666         /* f = */ BM_face_split(bm, l->f, v2, v1, NULL, l->e, FALSE);
667
668         return l;
669 }
670
671 /*
672  *                      BME_bevel_poly
673  *
674  *      Polygon inset tool:
675  *
676  *      Insets a polygon/face based on the flagss of its vertices
677  *      and edges. Used by the bevel tool only, for now.
678  *  The parameter "value" is the distance to inset (should be negative).
679  *  The parameter "options" is not currently used.
680  *
681  *      Returns -
682  *  A BMFace pointer to the resulting inner face.
683  */
684 static BMFace *BME_bevel_poly(BMesh *bm, BMFace *f, float value, int options, BME_TransData_Head *td)
685 {
686         BMLoop *l/*, *o */;
687         BME_TransData *vtd1, *vtd2;
688         float up_vec[3], vec1[3], vec2[3], vec3[3], fac1, fac2, max = -1;
689         int len, i;
690         BMIter iter;
691
692         zero_v3(up_vec);
693
694         /* find a good normal for this face (there's better ways, I'm sure) */
695         BM_ITER(l, &iter, bm, BM_LOOPS_OF_FACE, f) {
696                 BME_bevel_get_vec(vec1, l->v, l->next->v, td);
697                 BME_bevel_get_vec(vec2, l->prev->v, l->v, td);
698                 cross_v3_v3v3(vec3, vec2, vec1);
699                 add_v3_v3(up_vec, vec3);
700         }
701         normalize_v3(up_vec);
702
703         /* Can't use a BM_LOOPS_OF_FACE iterator here, because the loops are being modified
704          * and so the end condition will never hi */
705         for (l = BM_FACE_FIRST_LOOP(f)->prev, i = 0, len = f->len; i < len; i++, l = l->next) {
706                 if (BMO_elem_flag_test(bm, l->e, BME_BEVEL_BEVEL) && BMO_elem_flag_test(bm, l->e, BME_BEVEL_ORIG)) {
707                         max = 1.0f;
708                         l = BME_bevel_edge(bm, l, value, options, up_vec, td);
709                 }
710                 else if (BMO_elem_flag_test(bm, l->v, BME_BEVEL_BEVEL) &&
711                          BMO_elem_flag_test(bm, l->v, BME_BEVEL_ORIG) &&
712                         !BMO_elem_flag_test(bm, l->prev->e, BME_BEVEL_BEVEL))
713                 {
714                         max = 1.0f;
715                         l = BME_bevel_vert(bm, l, value, options, up_vec, td);
716                 }
717         }
718
719         f = l->f;
720
721         /* max pass */
722         if (value > 0.5f && max > 0) {
723                 max = -1;
724                 BM_ITER(l, &iter, bm, BM_LOOPS_OF_FACE, f) {
725                         if (BMO_elem_flag_test(bm, l->e, BME_BEVEL_BEVEL) || BMO_elem_flag_test(bm, l->e, BME_BEVEL_ORIG)) {
726                                 BME_bevel_get_vec(vec1, l->v, l->next->v, td);
727                                 vtd1 = BME_get_transdata(td, l->v);
728                                 vtd2 = BME_get_transdata(td, l->next->v);
729                                 if (vtd1->loc == NULL) {
730                                         fac1 = 0;
731                                 }
732                                 else {
733                                         copy_v3_v3(vec2, vtd1->vec);
734                                         mul_v3_fl(vec2, vtd1->factor);
735                                         if (dot_v3v3(vec1, vec1)) {
736                                                 project_v3_v3v3(vec2, vec2, vec1);
737                                                 fac1 = len_v3(vec2) / value;
738                                         }
739                                         else {
740                                                 fac1 = 0;
741                                         }
742                                 }
743                                 if (vtd2->loc == NULL) {
744                                         fac2 = 0;
745                                 }
746                                 else {
747                                         copy_v3_v3(vec3, vtd2->vec);
748                                         mul_v3_fl(vec3, vtd2->factor);
749                                         if (dot_v3v3(vec1, vec1)) {
750                                                 project_v3_v3v3(vec2, vec3, vec1);
751                                                 fac2 = len_v3(vec2) / value;
752                                         }
753                                         else {
754                                                 fac2 = 0;
755                                         }
756                                 }
757                                 if (fac1 || fac2) {
758                                         max = len_v3(vec1)/(fac1 + fac2);
759                                         if (vtd1->max && (*vtd1->max < 0 || max < *vtd1->max)) {
760                                                 *vtd1->max = max;
761                                         }
762                                         if (vtd2->max && (*vtd2->max < 0 || max < *vtd2->max)) {
763                                                 *vtd2->max = max;
764                                         }
765                                 }
766                         }
767                 }
768         }
769
770         /* return l->f; */
771         return NULL;
772 }
773
774 static void BME_bevel_add_vweight(BME_TransData_Head *td, BMesh *bm, BMVert *v, float weight, float factor, int options)
775 {
776         BME_TransData *vtd;
777
778         if (BMO_elem_flag_test(bm, v, BME_BEVEL_NONMAN)) {
779                 return;
780         }
781
782         BMO_elem_flag_enable(bm, v, BME_BEVEL_BEVEL);
783         if ((vtd = BME_get_transdata(td, v))) {
784                 if (options & BME_BEVEL_EMIN) {
785                         vtd->factor = 1.0;
786                         if (vtd->weight < 0 || weight < vtd->weight) {
787                                 vtd->weight = weight;
788                         }
789                 }
790                 else if (options & BME_BEVEL_EMAX) {
791                         vtd->factor = 1.0;
792                         if (weight > vtd->weight) {
793                                 vtd->weight = weight;
794                         }
795                 }
796                 else if (vtd->weight < 0) {
797                         vtd->factor = factor;
798                         vtd->weight = weight;
799                 }
800                 else {
801                         vtd->factor += factor; /* increment number of edges with weights (will be averaged) */
802                         vtd->weight += weight; /* accumulate all the weights */
803                 }
804         }
805         else {
806                 /* we'll use vtd->loc == NULL to mark that this vert is not moving */
807                 vtd = BME_assign_transdata(td, bm, v, v->co, NULL, NULL, NULL, factor, weight, -1, NULL);
808         }
809 }
810
811 static void bevel_init_verts(BMesh *bm, int options, BME_TransData_Head *td)
812 {
813         BMVert *v;
814         BMIter iter;
815         float weight;
816         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
817                 weight = 0.0f;
818                 if (!BMO_elem_flag_test(bm, v, BME_BEVEL_NONMAN)) {
819                         /* modifiers should not use selection */
820                         if (options & BME_BEVEL_SELECT) {
821                                 if (BM_elem_flag_test(v, BM_ELEM_SELECT)) {
822                                         weight = 1.0f;
823                                 }
824                         }
825                         /* bevel weight NYI */
826                         else if (options & BME_BEVEL_WEIGHT) {
827                                 weight = BM_elem_float_data_get(&bm->vdata, v, CD_BWEIGHT);
828                         }
829                         else {
830                                 weight = 1.0f;
831                         }
832
833                         if (weight > 0.0f) {
834                                 BMO_elem_flag_enable(bm, v, BME_BEVEL_BEVEL);
835                                 BME_assign_transdata(td, bm, v, v->co, v->co, NULL, NULL, 1.0, weight, -1, NULL);
836                         }
837                 }
838         }
839 }
840
841 static void bevel_init_edges(BMesh *bm, int options, BME_TransData_Head *td)
842 {
843         BMEdge *e;
844         int count;
845         float weight;
846         BMIter iter;
847         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
848                 weight = 0.0;
849                 if (!BMO_elem_flag_test(bm, e, BME_BEVEL_NONMAN)) {
850                         if (options & BME_BEVEL_SELECT) {
851                                 if (BM_elem_flag_test(e, BM_ELEM_SELECT)) weight = 1.0;
852                         }
853                         else if (options & BME_BEVEL_WEIGHT) {
854                                 weight = BM_elem_float_data_get(&bm->edata, e, CD_BWEIGHT);
855                         }
856                         else {
857                                 weight = 1.0;
858                         }
859
860                         if (weight > 0.0) {
861                                 BMO_elem_flag_enable(bm, e, BME_BEVEL_BEVEL);
862                                 BMO_elem_flag_enable(bm, e->v1, BME_BEVEL_BEVEL);
863                                 BMO_elem_flag_enable(bm, e->v2, BME_BEVEL_BEVEL);
864                                 BME_bevel_add_vweight(td, bm, e->v1, weight, 1.0, options);
865                                 BME_bevel_add_vweight(td, bm, e->v2, weight, 1.0, options);
866                         }
867                 }
868         }
869
870         /* clean up edges with 2 faces that share more than one edg */
871         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
872                 if (BMO_elem_flag_test(bm, e, BME_BEVEL_BEVEL)) {
873                         count = BM_face_share_edge_count(e->l->f, e->l->radial_next->f);
874                         if (count > 1) BMO_elem_flag_disable(bm, e, BME_BEVEL_BEVEL);
875                 }
876         }
877 }
878
879 static BMesh *BME_bevel_initialize(BMesh *bm, int options, int UNUSED(defgrp_index), float UNUSED(angle), BME_TransData_Head *td)
880 {
881         BMVert *v/*, *v2 */;
882         BMEdge *e/*, *curedg */;
883         BMFace *f;
884         BMIter iter;
885         int /* wire, */ len;
886
887         /* tag non-manifold geometr */
888         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
889                 BMO_elem_flag_enable(bm, v, BME_BEVEL_ORIG);
890                 if (v->e) {
891                         BME_assign_transdata(td, bm, v, v->co, v->co, NULL, NULL, 0, -1, -1, NULL);
892                         if (!BM_vert_is_manifold(v)) {
893                                 BMO_elem_flag_enable(bm, v, BME_BEVEL_NONMAN);
894                         }
895
896                         /* test wire ver */
897                         len = BM_vert_edge_count(v);
898                         if (len == 2 && BM_vert_is_wire(v))
899                                 BMO_elem_flag_disable(bm, v, BME_BEVEL_NONMAN);
900                 }
901                 else {
902                         BMO_elem_flag_enable(bm, v, BME_BEVEL_NONMAN);
903                 }
904         }
905
906         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
907                 BMO_elem_flag_enable(bm, e, BME_BEVEL_ORIG);
908                 if (!(BM_edge_is_boundary(e) || BM_edge_is_manifold(e))) {
909                         BMO_elem_flag_enable(bm, e->v1, BME_BEVEL_NONMAN);
910                         BMO_elem_flag_enable(bm, e->v2, BME_BEVEL_NONMAN);
911                         BMO_elem_flag_enable(bm, e, BME_BEVEL_NONMAN);
912                 }
913                 if (BMO_elem_flag_test(bm, e->v1, BME_BEVEL_NONMAN) || BMO_elem_flag_test(bm, e->v2, BME_BEVEL_NONMAN)) {
914                         BMO_elem_flag_enable(bm, e, BME_BEVEL_NONMAN);
915                 }
916         }
917
918         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
919                 BMO_elem_flag_enable(bm, f, BME_BEVEL_ORIG);
920         }
921
922         if (options & BME_BEVEL_VERT) {
923                 bevel_init_verts(bm, options, td);
924         }
925         else {
926                 bevel_init_edges(bm, options, td);
927         }
928
929         return bm;
930
931 }
932
933 #if 0
934
935 static BMesh *BME_bevel_reinitialize(BMesh *bm)
936 {
937         BMVert *v;
938         BMEdge *e;
939         BMFace *f;
940         BMIter iter;
941
942         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
943                 BMO_elem_flag_enable(bm, v, BME_BEVEL_ORIG);
944         }
945         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
946                 BMO_elem_flag_enable(bm, e, BME_BEVEL_ORIG);
947         }
948         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
949                 BMO_elem_flag_enable(bm, f, BME_BEVEL_ORIG);
950         }
951         return bm;
952
953 }
954
955 #endif
956
957 /**
958  *                      BME_bevel_mesh
959  *
960  *      Mesh beveling tool:
961  *
962  *      Bevels an entire mesh. It currently uses the flags of
963  *      its vertices and edges to track topological changes.
964  *  The parameter "value" is the distance to inset (should be negative).
965  *  The parameter "options" is not currently used.
966  *
967  *      Returns -
968  *  A BMesh pointer to the BM passed as a parameter.
969  */
970
971 static BMesh *BME_bevel_mesh(BMesh *bm, float value, int UNUSED(res), int options, int UNUSED(defgrp_index), BME_TransData_Head *td)
972 {
973         BMVert *v;
974         BMEdge *e, *curedge;
975         BMLoop *l, *l2;
976         BMFace *f;
977         BMIter iter;
978
979         /* unsigned int i, len; */
980
981         /* bevel poly */
982         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
983                 if (BMO_elem_flag_test(bm, f, BME_BEVEL_ORIG)) {
984                         BME_bevel_poly(bm, f, value, options, td);
985                 }
986         }
987
988         /* get rid of beveled edge */
989         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
990                 if (BMO_elem_flag_test(bm, e, BME_BEVEL_BEVEL) && BMO_elem_flag_test(bm, e, BME_BEVEL_ORIG)) {
991                         BM_faces_join_pair(bm, e->l->f, e->l->radial_next->f, e, TRUE);
992                 }
993         }
994
995         /* link up corners and cli */
996         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
997                 if (BMO_elem_flag_test(bm, v, BME_BEVEL_ORIG) && BMO_elem_flag_test(bm, v, BME_BEVEL_BEVEL)) {
998                         curedge = v->e;
999                         do {
1000                                 l = curedge->l;
1001                                 l2 = l->radial_next;
1002                                 if (l->v != v) l = l->next;
1003                                 if (l2->v != v) l2 = l2->next;
1004                                 if (l->f->len > 3)
1005                                         BM_face_split(bm, l->f, l->next->v, l->prev->v, &l, l->e, FALSE); /* clip this corner off */
1006                                 if (l2->f->len > 3)
1007                                         BM_face_split(bm, l2->f, l2->next->v, l2->prev->v, &l, l2->e, FALSE); /* clip this corner off */
1008                                 curedge = bmesh_disk_edge_next(curedge, v);
1009                         } while (curedge != v->e);
1010                         BME_Bevel_Dissolve_Disk(bm, v);
1011                 }
1012         }
1013
1014         /* Debug print, remov */
1015         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
1016                 if (f->len == 2) {
1017                         printf("warning");
1018                 }
1019         }
1020
1021         return bm;
1022 }
1023
1024 BMesh *BME_bevel(BMEditMesh *em, float value, int res, int options, int defgrp_index, float angle,
1025                  BME_TransData_Head **rtd, int do_tessface)
1026 {
1027         BMesh *bm = em->bm;
1028         BMVert *v;
1029         BMIter iter;
1030
1031         BME_TransData_Head *td;
1032         BME_TransData *vtd;
1033         int i;
1034         double fac = 1, d;
1035
1036         td = BME_init_transdata(BLI_MEMARENA_STD_BUFSIZE);
1037         /* recursion math courtesy of Martin Poirier (theeth) */
1038         for (i = 0; i < res - 1; i++) {
1039                 if (i == 0) fac += 1.0f / 3.0f; else fac += 1.0f / (3 * i * 2.0f);
1040         }
1041         d = 1.0f / fac;
1042
1043         for (i = 0; i < res || (res == 0 && i == 0); i++) {
1044                 BMO_push(bm, NULL);
1045                 BME_bevel_initialize(bm, options, defgrp_index, angle, td);
1046                 //if (i != 0) BME_bevel_reinitialize(bm);
1047                 bmesh_edit_begin(bm, 0);
1048                 BME_bevel_mesh(bm, (float)d, res, options, defgrp_index, td);
1049                 bmesh_edit_end(bm, 0);
1050                 d /= (i == 0) ? 3.0 : 2.0;
1051                 BMO_pop(bm);
1052         }
1053
1054         /* possibly needed when running as a tool (which is no longer functional)
1055          * but keep as an optioin for now */
1056         if (do_tessface) {
1057                 BMEdit_RecalcTessellation(em);
1058         }
1059
1060         /* interactive preview? */
1061         if (rtd) {
1062                 *rtd = td;
1063                 return bm;
1064         }
1065
1066         /* otherwise apply transforms */
1067         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
1068                 if ((vtd = BME_get_transdata(td, v))) {
1069                         if (vtd->max && (*vtd->max > 0 && value > *vtd->max)) {
1070                                 d = *vtd->max;
1071                         }
1072                         else {
1073                                 d = value;
1074                         }
1075                         madd_v3_v3v3fl(v->co, vtd->org, vtd->vec, vtd->factor * d);
1076                 }
1077         }
1078
1079         BME_free_transdata(td);
1080         return bm;
1081 }