More F-Modifier Tweaks:
[blender.git] / source / blender / blenkernel / intern / BME_tools.c
1 /**
2  * BME_tools.c    jan 2007
3  *
4  *      Functions for changing the topology of a mesh.
5  *
6  * $Id$
7  *
8  * ***** BEGIN GPL LICENSE BLOCK *****
9  *
10  * This program is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU General Public License
12  * as published by the Free Software Foundation; either version 2
13  * of the License, or (at your option) any later version.
14  *
15  * This program is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18  * GNU General Public License for more details.
19  *
20  * You should have received a copy of the GNU General Public License
21  * along with this program; if not, write to the Free Software Foundation,
22  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
23  *
24  * The Original Code is Copyright (C) 2004 Blender Foundation.
25  * All rights reserved.
26  *
27  * The Original Code is: all of this file.
28  *
29  * Contributor(s): Geoffrey Bantle and Levi Schooley.
30  *
31  * ***** END GPL LICENSE BLOCK *****
32  */
33
34 #include <math.h>
35
36 #include "MEM_guardedalloc.h"
37
38 #include "DNA_listBase.h"
39 #include "DNA_meshdata_types.h"
40 #include "DNA_mesh_types.h"
41 #include "DNA_object_types.h"
42
43 #include "BKE_utildefines.h"
44 #include "BKE_bmesh.h"
45 #include "BLI_math.h"
46 #include "BLI_blenlib.h"
47
48 /*split this all into a seperate bevel.c file in src*/
49
50 /* ------- Bevel code starts here -------- */
51
52 BME_TransData_Head *BME_init_transdata(int bufsize) {
53         BME_TransData_Head *td;
54
55         td = MEM_callocN(sizeof(BME_TransData_Head), "BMesh transdata header");
56         td->gh = BLI_ghash_new(BLI_ghashutil_ptrhash,BLI_ghashutil_ptrcmp);
57         td->ma = BLI_memarena_new(bufsize);
58         BLI_memarena_use_calloc(td->ma);
59
60         return td;
61 }
62
63 void BME_free_transdata(BME_TransData_Head *td) {
64         BLI_ghash_free(td->gh,NULL,NULL);
65         BLI_memarena_free(td->ma);
66         MEM_freeN(td);
67 }
68
69 BME_TransData *BME_assign_transdata(BME_TransData_Head *td, BME_Mesh *bm, BME_Vert *v,
70                 float *co, float *org, float *vec, float *loc,
71                 float factor, float weight, float maxfactor, float *max) {
72         BME_TransData *vtd;
73         int is_new = 0;
74
75         if (v == NULL) return NULL;
76
77         if ((vtd = BLI_ghash_lookup(td->gh, v)) == NULL && bm != NULL) {
78                 vtd = BLI_memarena_alloc(td->ma, sizeof(*vtd));
79                 BLI_ghash_insert(td->gh, v, vtd);
80                 td->len++;
81                 is_new = 1;
82         }
83
84         vtd->bm = bm;
85         vtd->v = v;
86         if (co != NULL) VECCOPY(vtd->co,co);
87         if (org == NULL && is_new) { VECCOPY(vtd->org,v->co); } /* default */
88         else if (org != NULL) VECCOPY(vtd->org,org);
89         if (vec != NULL) {
90                 VECCOPY(vtd->vec,vec);
91                 normalize_v3(vtd->vec);
92         }
93         vtd->loc = loc;
94
95         vtd->factor = factor;
96         vtd->weight = weight;
97         vtd->maxfactor = maxfactor;
98         vtd->max = max;
99
100         return vtd;
101 }
102
103 BME_TransData *BME_get_transdata(BME_TransData_Head *td, BME_Vert *v) {
104         BME_TransData *vtd;
105         vtd = BLI_ghash_lookup(td->gh, v);
106         return vtd;
107 }
108
109 /* a hack (?) to use the transdata memarena to allocate floats for use with the max limits */
110 float *BME_new_transdata_float(BME_TransData_Head *td) {
111         return BLI_memarena_alloc(td->ma, sizeof(float));
112 }
113
114 static int BME_is_nonmanifold_vert(BME_Mesh *bm, BME_Vert *v) {
115         BME_Edge *e, *oe;
116         BME_Loop *l;
117         int len, count, flag;
118
119         if (v->edge == NULL) {
120                 /* loose vert */
121                 return 1;
122         }
123
124         /* count edges while looking for non-manifold edges */
125         oe = v->edge;
126         for (len=0,e=v->edge; e != oe || (e == oe && len == 0); len++,e=BME_disk_nextedge(e,v)) {
127                 if (e->loop == NULL) {
128                         /* loose edge */
129                         return 1;
130                 }
131
132                 if (BME_cycle_length(&(e->loop->radial)) > 2) {
133                         /* edge shared by more than two faces */
134                         return 1;
135                 }
136         }
137
138         count = 1;
139         flag = 1;
140         e = NULL;
141         oe = v->edge;
142         l = oe->loop;
143         while(e != oe) {
144                 if (l->v == v) l = l->prev;
145                 else l = l->next;
146                 e = l->e;
147                 count++; /* count the edges */
148
149                 if (flag && l->radial.next->data == l) {
150                         /* we've hit the edge of an open mesh, reset once */
151                         flag = 0;
152                         count = 1;
153                         oe = e;
154                         e = NULL;
155                         l = oe->loop;
156                 }
157                 else if (l->radial.next->data == l) {
158                         /* break the loop */
159                         e = oe;
160                 }
161                 else {
162                         l = l->radial.next->data;
163                 }
164         }
165
166         if (count < len) {
167                 /* vert shared by multiple regions */
168                 return 1;
169         }
170
171         return 0;
172 }
173
174 /* a wrapper for BME_JFKE that [for now just] checks to
175  * make sure loop directions are compatible */
176 static BME_Poly *BME_JFKE_safe(BME_Mesh *bm, BME_Poly *f1, BME_Poly *f2, BME_Edge *e) {
177         BME_Loop *l1, *l2;
178
179         l1 = e->loop;
180         l2 = l1->radial.next->data;
181         if (l1->v == l2->v) {
182                 BME_loop_reverse(bm, f2);
183         }
184
185         return BME_JFKE(bm, f1, f2, e);
186 }
187
188 /* a wrapper for BME_SFME that transfers element flags */
189 static BME_Poly *BME_split_face(BME_Mesh *bm, BME_Poly *f, BME_Vert *v1, BME_Vert *v2, BME_Loop **nl, BME_Edge *example) {
190         BME_Poly *nf;
191         nf = BME_SFME(bm,f,v1,v2,nl);
192         nf->flag = f->flag;
193         /* if the edge was selected, select this face, too */
194         if (example && (example->flag & SELECT)) f->flag |= ME_FACE_SEL;
195         nf->h = f->h;
196         nf->mat_nr = f->mat_nr;
197         if (nl && example) {
198                 (*nl)->e->flag = example->flag;
199                 (*nl)->e->h = example->h;
200                 (*nl)->e->crease = example->crease;
201                 (*nl)->e->bweight = example->bweight;
202         }
203
204         return nf;
205 }
206
207
208 #if 0
209 static void BME_data_interp_from_verts(BME_Mesh *bm, BME_Vert *v1, BME_Vert *v2, BME_Vert *v, float fac)
210 {
211         void *src[2];
212         float w[2];
213         if (v1->data && v2->data) {
214                 src[0]= v1->data;
215                 src[1]= v2->data;
216                 w[0] = 1.0f-fac;
217                 w[1] = fac;
218                 CustomData_bmesh_interp(&bm->vdata, src, w, NULL, 2, v->data);
219         }
220 }
221 #endif
222
223
224 static void BME_data_facevert_edgesplit(BME_Mesh *bm, BME_Vert *v1, BME_Vert *v2, BME_Vert *v, BME_Edge *e1, float fac){
225         void *src[2];
226         float w[2];
227         BME_Loop *l=NULL, *v1loop = NULL, *vloop = NULL, *v2loop = NULL;
228         
229         w[0] = 1.0f - fac;
230         w[1] = fac;
231
232         if(!e1->loop) return;
233         l = e1->loop;
234         do{
235                 if(l->v == v1){ 
236                         v1loop = l;
237                         vloop = v1loop->next;
238                         v2loop = vloop->next;
239                 }else if(l->v == v){
240                         v1loop = l->next;
241                         vloop = l;
242                         v2loop = l->prev;
243                         
244                 }
245
246                 src[0] = v1loop->data;
247                 src[1] = v2loop->data;                                  
248
249                 CustomData_bmesh_interp(&bm->ldata, src,w, NULL, 2, vloop->data);                               
250                 l = l->radial.next->data;
251         }while(l!=e1->loop);
252 }
253
254
255 /* a wrapper for BME_SEMV that transfers element flags */ /*add custom data interpolation in here!*/
256 static BME_Vert *BME_split_edge(BME_Mesh *bm, BME_Vert *v, BME_Edge *e, BME_Edge **ne, float percent) {
257         BME_Vert *nv, *v2;
258         float len;
259
260         v2 = BME_edge_getothervert(e,v);
261         nv = BME_SEMV(bm,v,e,ne);
262         if (nv == NULL) return NULL;
263         VECSUB(nv->co,v2->co,v->co);
264         len = len_v3(nv->co);
265         VECADDFAC(nv->co,v->co,nv->co,len*percent);
266         nv->flag = v->flag;
267         nv->bweight = v->bweight;
268         if (ne) {
269                 (*ne)->flag = e->flag;
270                 (*ne)->h = e->h;
271                 (*ne)->crease = e->crease;
272                 (*ne)->bweight = e->bweight;
273         }
274         /*v->nv->v2*/
275         BME_data_facevert_edgesplit(bm,v2, v, nv, e, 0.75);     
276         return nv;
277 }
278
279 static void BME_collapse_vert(BME_Mesh *bm, BME_Edge *ke, BME_Vert *kv, float fac){
280         void *src[2];
281         float w[2];
282         BME_Loop *l=NULL, *kvloop=NULL, *tvloop=NULL;
283         BME_Vert *tv = BME_edge_getothervert(ke,kv);
284
285         w[0] = 1.0f - fac;
286         w[1] = fac;
287
288         if(ke->loop){
289                 l = ke->loop;
290                 do{
291                         if(l->v == tv && l->next->v == kv){
292                                 tvloop = l;
293                                 kvloop = l->next;
294
295                                 src[0] = kvloop->data;
296                                 src[1] = tvloop->data;
297                                 CustomData_bmesh_interp(&bm->ldata, src,w, NULL, 2, kvloop->data);                                                              
298                         }
299                         l=l->radial.next->data;
300                 }while(l!=ke->loop);
301         }
302         BME_JEKV(bm,ke,kv);
303 }
304
305
306
307 static int BME_bevel_is_split_vert(BME_Loop *l) {
308         /* look for verts that have already been added to the edge when
309          * beveling other polys; this can be determined by testing the
310          * vert and the edges around it for originality
311          */
312         if ((l->v->tflag1 & BME_BEVEL_ORIG)==0
313                         && (l->e->tflag1 & BME_BEVEL_ORIG)
314                         && (l->prev->e->tflag1 & BME_BEVEL_ORIG))
315         {
316                 return 1;
317         }
318         return 0;
319 }
320
321 /* get a vector, vec, that points from v1->co to wherever makes sense to
322  * the bevel operation as a whole based on the relationship between v1 and v2
323  * (won't necessarily be a vec from v1->co to v2->co, though it probably will be);
324  * the return value is -1 for failure, 0 if we used vert co's, and 1 if we used transform origins */
325 static int BME_bevel_get_vec(float *vec, BME_Vert *v1, BME_Vert *v2, BME_TransData_Head *td) {
326         BME_TransData *vtd1, *vtd2;
327
328         vtd1 = BME_get_transdata(td,v1);
329         vtd2 = BME_get_transdata(td,v2);
330         if (!vtd1 || !vtd2) {
331                 //printf("BME_bevel_get_vec() got called without proper BME_TransData\n");
332                 return -1;
333         }
334
335         /* compare the transform origins to see if we can use the vert co's;
336          * if they belong to different origins, then we will use the origins to determine
337          * the vector */
338         if (compare_v3v3(vtd1->org,vtd2->org,0.000001f)) {
339                 VECSUB(vec,v2->co,v1->co);
340                 if (len_v3(vec) < 0.000001f) {
341                         mul_v3_fl(vec,0);
342                 }
343                 return 0;
344         }
345         else {
346                 VECSUB(vec,vtd2->org,vtd1->org);
347                 if (len_v3(vec) < 0.000001f) {
348                         mul_v3_fl(vec,0);
349                 }
350                 return 1;
351         }
352 }
353
354 /* "Projects" a vector perpendicular to vec2 against vec1, such that
355  * the projected vec1 + vec2 has a min distance of 1 from the "edge" defined by vec2.
356  * note: the direction, is_forward, is used in conjunction with up_vec to determine
357  * whether this is a convex or concave corner. If it is a concave corner, it will
358  * be projected "backwards." If vec1 is before vec2, is_forward should be 0 (we are projecting backwards).
359  * vec1 is the vector to project onto (expected to be normalized)
360  * vec2 is the direction of projection (pointing away from vec1)
361  * up_vec is used for orientation (expected to be normalized)
362  * returns the length of the projected vector that lies along vec1 */
363 static float BME_bevel_project_vec(float *vec1, float *vec2, float *up_vec, int is_forward, BME_TransData_Head *td) {
364         float factor, vec3[3], tmp[3],c1,c2;
365
366         cross_v3_v3v3(tmp,vec1,vec2);
367         normalize_v3(tmp);
368         factor = dot_v3v3(up_vec,tmp);
369         if ((factor > 0 && is_forward) || (factor < 0 && !is_forward)) {
370                 cross_v3_v3v3(vec3,vec2,tmp); /* hmm, maybe up_vec should be used instead of tmp */
371         }
372         else {
373                 cross_v3_v3v3(vec3,tmp,vec2); /* hmm, maybe up_vec should be used instead of tmp */
374         }
375         normalize_v3(vec3);
376         c1 = dot_v3v3(vec3,vec1);
377         c2 = dot_v3v3(vec1,vec1);
378         if (fabs(c1) < 0.000001f || fabs(c2) < 0.000001f) {
379                 factor = 0.0f;
380         }
381         else {
382                 factor = c2/c1;
383         }
384
385         return factor;
386 }
387
388 /* BME_bevel_split_edge() is the main math work-house; its responsibilities are:
389  * using the vert and the loop passed, get or make the split vert, set its coordinates
390  * and transform properties, and set the max limits.
391  * Finally, return the split vert. */
392 static BME_Vert *BME_bevel_split_edge(BME_Mesh *bm, BME_Vert *v, BME_Vert *v1, BME_Loop *l, float *up_vec, float value, BME_TransData_Head *td) {
393         BME_TransData *vtd, *vtd1, *vtd2;
394         BME_Vert *sv, *v2, *v3, *ov;
395         BME_Loop *lv1, *lv2;
396         BME_Edge *ne, *e1, *e2;
397         float maxfactor, scale, len, dis, vec1[3], vec2[3], t_up_vec[3];
398         int is_edge, forward, is_split_vert;
399
400         if (l == NULL) {
401                 /* what you call operator overloading in C :)
402                  * I wanted to use the same function for both wire edges and poly loops
403                  * so... here we walk around edges to find the needed verts */
404                 forward = 1;
405                 is_split_vert = 0;
406                 if (v->edge == NULL) {
407                         //printf("We can't split a loose vert's edge!\n");
408                         return NULL;
409                 }
410                 e1 = v->edge; /* we just use the first two edges */
411                 e2 = BME_disk_nextedge(v->edge, v);
412                 if (e1 == e2) {
413                         //printf("You need at least two edges to use BME_bevel_split_edge()\n");
414                         return NULL;
415                 }
416                 v2 = BME_edge_getothervert(e1, v);
417                 v3 = BME_edge_getothervert(e2, v);
418                 if (v1 != v2 && v1 != v3) {
419                         //printf("Error: more than 2 edges in v's disk cycle, or v1 does not share an edge with v\n");
420                         return NULL;
421                 }
422                 if (v1 == v2) {
423                         v2 = v3;
424                 }
425                 else {
426                         e1 = e2;
427                 }
428                 ov = BME_edge_getothervert(e1,v);
429                 sv = BME_split_edge(bm,v,e1,&ne,0);
430                 //BME_data_interp_from_verts(bm, v, ov, sv, 0.25); /*this is technically wrong...*/
431                 //BME_data_interp_from_faceverts(bm, v, ov, sv, 0.25);
432                 //BME_data_interp_from_faceverts(bm, ov, v, sv, 0.25);
433                 BME_assign_transdata(td, bm, sv, sv->co, sv->co, NULL, sv->co, 0, -1, -1, NULL); /* quick default */
434                 sv->tflag1 |= BME_BEVEL_BEVEL;
435                 ne->tflag1 = BME_BEVEL_ORIG; /* mark edge as original, even though it isn't */
436                 BME_bevel_get_vec(vec1,v1,v,td);
437                 BME_bevel_get_vec(vec2,v2,v,td);
438                 cross_v3_v3v3(t_up_vec,vec1,vec2);
439                 normalize_v3(t_up_vec);
440                 up_vec = t_up_vec;
441         }
442         else {
443                 /* establish loop direction */
444                 if (l->v == v) {
445                         forward = 1;
446                         lv1 = l->next;
447                         lv2 = l->prev;
448                         v1 = l->next->v;
449                         v2 = l->prev->v;
450                 }
451                 else if (l->next->v == v) {
452                         forward = 0;
453                         lv1 = l;
454                         lv2 = l->next->next;
455                         v1 = l->v;
456                         v2 = l->next->next->v;
457                 }
458                 else {
459                         //printf("ERROR: BME_bevel_split_edge() - v must be adjacent to l\n");
460                         return NULL;
461                 }
462
463                 if (BME_bevel_is_split_vert(lv1)) {
464                         is_split_vert = 1;
465                         sv = v1;
466                         if (forward) v1 = l->next->next->v;
467                         else v1 = l->prev->v;
468                 }
469                 else {
470                         is_split_vert = 0;
471                         ov = BME_edge_getothervert(l->e,v);
472                         sv = BME_split_edge(bm,v,l->e,&ne,0);
473                         //BME_data_interp_from_verts(bm, v, ov, sv, 0.25); /*this is technically wrong...*/
474                         //BME_data_interp_from_faceverts(bm, v, ov, sv, 0.25);
475                         //BME_data_interp_from_faceverts(bm, ov, v, sv, 0.25);
476                         BME_assign_transdata(td, bm, sv, sv->co, sv->co, NULL, sv->co, 0, -1, -1, NULL); /* quick default */
477                         sv->tflag1 |= BME_BEVEL_BEVEL;
478                         ne->tflag1 = BME_BEVEL_ORIG; /* mark edge as original, even though it isn't */
479                 }
480
481                 if (BME_bevel_is_split_vert(lv2)) {
482                         if (forward) v2 = lv2->prev->v;
483                         else v2 = lv2->next->v;
484                 }
485         }
486
487         is_edge = BME_bevel_get_vec(vec1,v,v1,td); /* get the vector we will be projecting onto */
488         BME_bevel_get_vec(vec2,v,v2,td); /* get the vector we will be projecting parallel to */
489         len = len_v3(vec1);
490         normalize_v3(vec1);
491
492         vtd = BME_get_transdata(td, sv);
493         vtd1 = BME_get_transdata(td, v);
494         vtd2 = BME_get_transdata(td,v1);
495
496         if (vtd1->loc == NULL) {
497                 /* this is a vert with data only for calculating initial weights */
498                 if (vtd1->weight < 0) {
499                         vtd1->weight = 0;
500                 }
501                 scale = vtd1->weight/vtd1->factor;
502                 if (!vtd1->max) {
503                         vtd1->max = BME_new_transdata_float(td);
504                         *vtd1->max = -1;
505                 }
506         }
507         else {
508                 scale = vtd1->weight;
509         }
510         vtd->max = vtd1->max;
511
512         if (is_edge && vtd1->loc != NULL) {
513                 maxfactor = vtd1->maxfactor;
514         }
515         else {
516                 maxfactor = scale*BME_bevel_project_vec(vec1,vec2,up_vec,forward,td);
517                 if (vtd->maxfactor > 0 && vtd->maxfactor < maxfactor) {
518                         maxfactor = vtd->maxfactor;
519                 }
520         }
521
522         dis = (v1->tflag1 & BME_BEVEL_ORIG)? len/3 : len/2;
523         if (is_edge || dis > maxfactor*value) {
524                 dis = maxfactor*value;
525         }
526         VECADDFAC(sv->co,v->co,vec1,dis);
527         VECSUB(vec1,sv->co,vtd1->org);
528         dis = len_v3(vec1);
529         normalize_v3(vec1);
530         BME_assign_transdata(td, bm, sv, vtd1->org, vtd1->org, vec1, sv->co, dis, scale, maxfactor, vtd->max);
531
532         return sv;
533 }
534
535 static float BME_bevel_set_max(BME_Vert *v1, BME_Vert *v2, float value, BME_TransData_Head *td) {
536         BME_TransData *vtd1, *vtd2;
537         float max, fac1, fac2, vec1[3], vec2[3], vec3[3];
538
539         BME_bevel_get_vec(vec1,v1,v2,td);
540         vtd1 = BME_get_transdata(td,v1);
541         vtd2 = BME_get_transdata(td,v2);
542
543         if (vtd1->loc == NULL) {
544                 fac1 = 0;
545         }
546         else {
547                 VECCOPY(vec2,vtd1->vec);
548                 mul_v3_fl(vec2,vtd1->factor);
549                 if (dot_v3v3(vec1, vec1)) {
550                         project_v3_v3v3(vec2,vec2,vec1);
551                         fac1 = len_v3(vec2)/value;
552                 }
553                 else {
554                         fac1 = 0;
555                 }
556         }
557
558         if (vtd2->loc == NULL) {
559                 fac2 = 0;
560         }
561         else {
562                 VECCOPY(vec3,vtd2->vec);
563                 mul_v3_fl(vec3,vtd2->factor);
564                 if (dot_v3v3(vec1, vec1)) {
565                         project_v3_v3v3(vec2,vec3,vec1);
566                         fac2 = len_v3(vec2)/value;
567                 }
568                 else {
569                         fac2 = 0;
570                 }
571         }
572
573         if (fac1 || fac2) {
574                 max = len_v3(vec1)/(fac1 + fac2);
575                 if (vtd1->max && (*vtd1->max < 0 || max < *vtd1->max)) {
576                         *vtd1->max = max;
577                 }
578                 if (vtd2->max && (*vtd2->max < 0 || max < *vtd2->max)) {
579                         *vtd2->max = max;
580                 }
581         }
582         else {
583                 max = -1;
584         }
585
586         return max;
587 }
588
589 static BME_Vert *BME_bevel_wire(BME_Mesh *bm, BME_Vert *v, float value, int res, int options, BME_TransData_Head *td) {
590         BME_Vert *ov1, *ov2, *v1, *v2;
591
592         ov1 = BME_edge_getothervert(v->edge, v);
593         ov2 = BME_edge_getothervert(BME_disk_nextedge(v->edge, v), v);
594
595         /* split the edges */
596         v1 = BME_bevel_split_edge(bm,v,ov1,NULL,NULL,value,td);
597         v1->tflag1 |= BME_BEVEL_NONMAN;
598         v2 = BME_bevel_split_edge(bm,v,ov2,NULL,NULL,value,td);
599         v2->tflag1 |= BME_BEVEL_NONMAN;
600
601         if (value > 0.5) {
602                 BME_bevel_set_max(v1,ov1,value,td);
603                 BME_bevel_set_max(v2,ov2,value,td);
604         }
605
606         /* remove the original vert */
607         if (res) {
608                 BME_JEKV(bm,v->edge,v);
609         }
610
611         return v1;
612 }
613
614 static BME_Loop *BME_bevel_edge(BME_Mesh *bm, BME_Loop *l, float value, int options, float *up_vec, BME_TransData_Head *td) {
615         BME_Vert *v1, *v2, *kv;
616         BME_Loop *kl=NULL, *nl;
617         BME_Edge *e;
618         BME_Poly *f;
619
620         f = l->f;
621         e = l->e;
622
623         if ((l->e->tflag1 & BME_BEVEL_BEVEL) == 0
624                 && ((l->v->tflag1 & BME_BEVEL_BEVEL) || (l->next->v->tflag1 & BME_BEVEL_BEVEL)))
625         { /* sanity check */
626                 return l;
627         }
628
629         /* checks and operations for prev edge */
630         /* first, check to see if this edge was inset previously */
631         if ((l->prev->e->tflag1 & BME_BEVEL_ORIG) == 0
632                 && (l->v->tflag1 & BME_BEVEL_NONMAN) == 0) {
633                 kl = l->prev->radial.next->data;
634                 if (kl->v == l->v) kl = kl->prev;
635                 else kl = kl->next;
636                 kv = l->v;
637         }
638         else {
639                 kv = NULL;
640         }
641         /* get/make the first vert to be used in SFME */
642         if (l->v->tflag1 & BME_BEVEL_NONMAN){
643                 v1 = l->v;
644         }
645         else { /* we'll need to split the previous edge */
646                 v1 = BME_bevel_split_edge(bm,l->v,NULL,l->prev,up_vec,value,td);
647         }
648         /* if we need to clean up geometry... */
649         if (kv) {
650                 l = l->next;
651                 if (kl->v == kv) {
652                         BME_split_face(bm,kl->f,kl->prev->v,kl->next->v,&nl,kl->prev->e);
653                         BME_JFKE(bm,((BME_Loop*)kl->prev->radial.next->data)->f,kl->f,kl->prev->e);
654                         BME_collapse_vert(bm, kl->e, kv, 1.0);
655                         //BME_JEKV(bm,kl->e,kv);
656                         
657                 }
658                 else {
659                         BME_split_face(bm,kl->f,kl->next->next->v,kl->v,&nl,kl->next->e);
660                         BME_JFKE(bm,((BME_Loop*)kl->next->radial.next->data)->f,kl->f,kl->next->e);
661                         BME_collapse_vert(bm, kl->e, kv, 1.0);
662                         //BME_JEKV(bm,kl->e,kv);
663                 }
664                 l = l->prev;
665         }
666
667         /* checks and operations for the next edge */
668         /* first, check to see if this edge was inset previously  */
669         if ((l->next->e->tflag1 & BME_BEVEL_ORIG) == 0
670                 && (l->next->v->tflag1 & BME_BEVEL_NONMAN) == 0) {
671                 kl = l->next->radial.next->data;
672                 if (kl->v == l->next->v) kl = kl->prev;
673                 else kl = kl->next;
674                 kv = l->next->v;
675         }
676         else {
677                 kv = NULL;
678         }
679         /* get/make the second vert to be used in SFME */
680         if (l->next->v->tflag1 & BME_BEVEL_NONMAN) {
681                 v2 = l->next->v;
682         }
683         else { /* we'll need to split the next edge */
684                 v2 = BME_bevel_split_edge(bm,l->next->v,NULL,l->next,up_vec,value,td);
685         }
686         /* if we need to clean up geometry... */
687         if (kv) {
688                 if (kl->v == kv) {
689                         BME_split_face(bm,kl->f,kl->prev->v,kl->next->v,&nl,kl->prev->e);
690                         BME_JFKE(bm,((BME_Loop*)kl->prev->radial.next->data)->f,kl->f,kl->prev->e);
691                         BME_collapse_vert(bm, kl->e, kv, 1.0);
692                         //BME_JEKV(bm,kl->e,kv);
693                 }
694                 else {
695                         BME_split_face(bm,kl->f,kl->next->next->v,kl->v,&nl,kl->next->e);
696                         BME_JFKE(bm,((BME_Loop*)kl->next->radial.next->data)->f,kl->f,kl->next->e);
697                         BME_collapse_vert(bm, kl->e, kv, 1.0);
698                         //BME_JEKV(bm,kl->e,kv);
699                 }
700         }
701
702         if ((v1->tflag1 & BME_BEVEL_NONMAN)==0 || (v2->tflag1 & BME_BEVEL_NONMAN)==0) {
703                 BME_split_face(bm,f,v2,v1,&l,e);
704                 l->e->tflag1 = BME_BEVEL_BEVEL;
705                 l = l->radial.next->data;
706         }
707
708         if (l->f != f){
709                 //printf("Whoops! You got something out of order in BME_bevel_edge()!\n");
710         }
711
712         return l;
713 }
714
715 static BME_Loop *BME_bevel_vert(BME_Mesh *bm, BME_Loop *l, float value, int options, float *up_vec, BME_TransData_Head *td) {
716         BME_Vert *v1, *v2;
717         BME_Poly *f;
718
719         /* get/make the first vert to be used in SFME */
720         /* may need to split the previous edge */
721         v1 = BME_bevel_split_edge(bm,l->v,NULL,l->prev,up_vec,value,td);
722
723         /* get/make the second vert to be used in SFME */
724         /* may need to split this edge (so move l) */
725         l = l->prev;
726         v2 = BME_bevel_split_edge(bm,l->next->v,NULL,l->next,up_vec,value,td);
727         l = l->next->next;
728
729         /* "cut off" this corner */
730         f = BME_split_face(bm,l->f,v2,v1,NULL,l->e);
731
732         return l;
733 }
734
735 /**
736  *                      BME_bevel_poly
737  *
738  *      Polygon inset tool:
739  *
740  *      Insets a polygon/face based on the tflag1's of its vertices
741  *      and edges. Used by the bevel tool only, for now.
742  *  The parameter "value" is the distance to inset (should be negative).
743  *  The parameter "options" is not currently used.
744  *
745  *      Returns -
746  *  A BME_Poly pointer to the resulting inner face.
747 */
748 static BME_Poly *BME_bevel_poly(BME_Mesh *bm, BME_Poly *f, float value, int options, BME_TransData_Head *td) {
749         BME_Loop *l, *ol;
750         BME_TransData *vtd1, *vtd2;
751         float up_vec[3], vec1[3], vec2[3], vec3[3], fac1, fac2, max = -1;
752         int len, i;
753
754         up_vec[0] = 0.0f;
755         up_vec[1] = 0.0f;
756         up_vec[2] = 0.0f;
757         /* find a good normal for this face (there's better ways, I'm sure) */
758         ol = f->loopbase;
759         l = ol->next;
760         for (i=0,ol=f->loopbase,l=ol->next; l->next!=ol; l=l->next) {
761                 BME_bevel_get_vec(vec1,l->next->v,ol->v,td);
762                 BME_bevel_get_vec(vec2,l->v,ol->v,td);
763                 cross_v3_v3v3(vec3,vec2,vec1);
764                 VECADD(up_vec,up_vec,vec3);
765                 i++;
766         }
767         mul_v3_fl(up_vec,1.0f/i);
768         normalize_v3(up_vec);
769
770         for (i=0,len=f->len; i<len; i++,l=l->next) {
771                 if ((l->e->tflag1 & BME_BEVEL_BEVEL) && (l->e->tflag1 & BME_BEVEL_ORIG)) {
772                         max = 1.0f;
773                         l = BME_bevel_edge(bm, l, value, options, up_vec, td);
774                 }
775                 else if ((l->v->tflag1 & BME_BEVEL_BEVEL) && (l->v->tflag1 & BME_BEVEL_ORIG) && (l->prev->e->tflag1 & BME_BEVEL_BEVEL) == 0) {
776                         max = 1.0f;
777                         l = BME_bevel_vert(bm, l, value, options, up_vec, td);
778                 }
779         }
780
781         /* max pass */
782         if (value > 0.5 && max > 0) {
783                 max = -1;
784                 for (i=0,len=f->len; i<len; i++,l=l->next) {
785                         if ((l->e->tflag1 & BME_BEVEL_BEVEL) || (l->e->tflag1 & BME_BEVEL_ORIG)) {
786                                 BME_bevel_get_vec(vec1,l->v,l->next->v,td);
787                                 vtd1 = BME_get_transdata(td,l->v);
788                                 vtd2 = BME_get_transdata(td,l->next->v);
789                                 if (vtd1->loc == NULL) {
790                                         fac1 = 0;
791                                 }
792                                 else {
793                                         VECCOPY(vec2,vtd1->vec);
794                                         mul_v3_fl(vec2,vtd1->factor);
795                                         if (dot_v3v3(vec1, vec1)) {
796                                                 project_v3_v3v3(vec2,vec2,vec1);
797                                                 fac1 = len_v3(vec2)/value;
798                                         }
799                                         else {
800                                                 fac1 = 0;
801                                         }
802                                 }
803                                 if (vtd2->loc == NULL) {
804                                         fac2 = 0;
805                                 }
806                                 else {
807                                         VECCOPY(vec3,vtd2->vec);
808                                         mul_v3_fl(vec3,vtd2->factor);
809                                         if (dot_v3v3(vec1, vec1)) {
810                                                 project_v3_v3v3(vec2,vec3,vec1);
811                                                 fac2 = len_v3(vec2)/value;
812                                         }
813                                         else {
814                                                 fac2 = 0;
815                                         }
816                                 }
817                                 if (fac1 || fac2) {
818                                         max = len_v3(vec1)/(fac1 + fac2);
819                                         if (vtd1->max && (*vtd1->max < 0 || max < *vtd1->max)) {
820                                                 *vtd1->max = max;
821                                         }
822                                         if (vtd2->max && (*vtd2->max < 0 || max < *vtd2->max)) {
823                                                 *vtd2->max = max;
824                                         }
825                                 }
826                         }
827                 }
828         }
829
830         return l->f;
831 }
832
833 static void BME_bevel_add_vweight(BME_TransData_Head *td, BME_Mesh *bm, BME_Vert *v, float weight, float factor, int options) {
834         BME_TransData *vtd;
835
836         if (v->tflag1 & BME_BEVEL_NONMAN) return;
837         v->tflag1 |= BME_BEVEL_BEVEL;
838         if ( (vtd = BME_get_transdata(td, v)) ) {
839                 if (options & BME_BEVEL_EMIN) {
840                         vtd->factor = 1.0;
841                         if (vtd->weight < 0 || weight < vtd->weight) {
842                                 vtd->weight = weight;
843                         }
844                 }
845                 else if (options & BME_BEVEL_EMAX) {
846                         vtd->factor = 1.0;
847                         if (weight > vtd->weight) {
848                                 vtd->weight = weight;
849                         }
850                 }
851                 else if (vtd->weight < 0) {
852                         vtd->factor = factor;
853                         vtd->weight = weight;
854                 }
855                 else {
856                         vtd->factor += factor; /* increment number of edges with weights (will be averaged) */
857                         vtd->weight += weight; /* accumulate all the weights */
858                 }
859         }
860         else {
861                 /* we'll use vtd->loc == NULL to mark that this vert is not moving */
862                 vtd = BME_assign_transdata(td, bm, v, v->co, NULL, NULL, NULL, factor, weight, -1, NULL);
863         }
864 }
865
866 static float BME_bevel_get_angle(BME_Mesh *bm, BME_Edge *e, BME_Vert *v) {
867         BME_Vert *v1, *v2;
868         BME_Loop *l1, *l2;
869         float vec1[3], vec2[3], vec3[3], vec4[3];
870
871         l1 = e->loop;
872         l2 = e->loop->radial.next->data;
873         if (l1->v == v) {
874                 v1 = l1->prev->v;
875                 v2 = l1->next->v;
876         }
877         else {
878                 v1 = l1->next->next->v;
879                 v2 = l1->v;
880         }
881         VECSUB(vec1,v1->co,v->co);
882         VECSUB(vec2,v2->co,v->co);
883         cross_v3_v3v3(vec3,vec1,vec2);
884
885         l1 = l2;
886         if (l1->v == v) {
887                 v1 = l1->prev->v;
888                 v2 = l1->next->v;
889         }
890         else {
891                 v1 = l1->next->next->v;
892                 v2 = l1->v;
893         }
894         VECSUB(vec1,v1->co,v->co);
895         VECSUB(vec2,v2->co,v->co);
896         cross_v3_v3v3(vec4,vec2,vec1);
897
898         normalize_v3(vec3);
899         normalize_v3(vec4);
900
901         return dot_v3v3(vec3,vec4);
902 }
903 static int BME_face_sharededges(BME_Poly *f1, BME_Poly *f2){
904         BME_Loop *l;
905         int count = 0;
906         
907         l = f1->loopbase;
908         do{
909                 if(BME_radial_find_face(l->e,f2)) count++;
910                 l = l->next;
911         }while(l != f1->loopbase);
912         
913         return count;
914 }
915 /**
916  *                      BME_bevel_initialize
917  *
918  *      Prepare the mesh for beveling:
919  *
920  *      Sets the tflag1's of the mesh elements based on the options passed.
921  *
922  *      Returns -
923  *  A BME_Mesh pointer to the BMesh passed as a parameter.
924 */
925 static BME_Mesh *BME_bevel_initialize(BME_Mesh *bm, int options, int defgrp_index, float angle, BME_TransData_Head *td) {
926         BME_Vert *v;
927         BME_Edge *e;
928         BME_Poly *f;
929         BME_TransData *vtd;
930         MDeformVert *dvert;
931         MDeformWeight *dw;
932         int len;
933         float weight, threshold;
934
935         /* vert pass */
936         for (v=bm->verts.first; v; v=v->next) {
937                 dvert = NULL;
938                 dw = NULL;
939                 v->tflag1 = BME_BEVEL_ORIG;
940                 /* originally coded, a vertex gets tagged with BME_BEVEL_BEVEL in this pass if
941                  * the vert is manifold (or is shared by only two edges - wire bevel)
942                  * BME_BEVEL_SELECT is passed and the vert has v->flag&SELECT or
943                  * BME_BEVEL_VWEIGHT is passed, and the vert has a defgrp and weight
944                  * BME_BEVEL_ANGLE is not passed
945                  * BME_BEVEL_EWEIGHT is not passed
946                  */
947                 /* originally coded, a vertex gets tagged with BME_BEVEL_NONMAN in this pass if
948                  * the vert is loose, shared by multiple regions, or is shared by wire edges
949                  * note: verts belonging to edges of open meshes are not tagged with BME_BEVEL_NONMAN
950                  */
951                 /* originally coded, a vertex gets a transform weight set in this pass if
952                  * BME_BEVEL_VWEIGHT is passed, and the vert has a defgrp and weight
953                  */
954
955                 /* get disk cycle length */
956                 if (v->edge == NULL) {
957                         len = 0;
958                 }
959                 else {
960                         len = BME_cycle_length(BME_disk_getpointer(v->edge,v));
961                         /* we'll assign a default transform data to every vert (except the loose ones) */
962                         vtd = BME_assign_transdata(td, bm, v, v->co, v->co, NULL, NULL, 0, -1, -1, NULL);
963                 }
964
965                 /* check for non-manifold vert */
966                 if (BME_is_nonmanifold_vert(bm,v)) {
967                         v->tflag1 |= BME_BEVEL_NONMAN;
968                 }
969
970                 /* BME_BEVEL_BEVEL tests */
971                 if ((v->tflag1 & BME_BEVEL_NONMAN) == 0 || len == 2) { /* either manifold vert, or wire vert */
972                         if (((options & BME_BEVEL_SELECT) && (v->flag & SELECT))
973                                 || ((options & BME_BEVEL_WEIGHT) && (options & BME_BEVEL_VERT)) /* use weights for verts */
974                                 || ((options & BME_BEVEL_ANGLE) == 0
975                                         && (options & BME_BEVEL_SELECT) == 0
976                                         && (options & BME_BEVEL_WEIGHT) == 0))
977                         {
978                                 if (options & BME_BEVEL_WEIGHT) {
979                                         /* do vert weight stuff */
980                                         //~ dvert = CustomData_em_get(&bm->vdata,v->data,CD_MDEFORMVERT);
981                                         //~ if (!dvert) continue;
982                                         //~ for (i = 0; i < dvert->totweight; ++i) {
983                                                 //~ if(dvert->dw[i].def_nr == defgrp_index) {
984                                                         //~ dw = &dvert->dw[i];
985                                                         //~ break;
986                                                 //~ }
987                                         //~ }
988                                         //~ if (!dw || dw->weight == 0.0) continue;
989                                         if (v->bweight == 0.0) continue;
990                                         vtd = BME_assign_transdata(td, bm, v, v->co, v->co, NULL, NULL, 1.0, v->bweight, -1, NULL);
991                                         v->tflag1 |= BME_BEVEL_BEVEL;
992                                 }
993                                 else {
994                                         vtd = BME_assign_transdata(td, bm, v, v->co, v->co, NULL, NULL, 1.0, 1.0, -1, NULL);
995                                         v->tflag1 |= BME_BEVEL_BEVEL;
996                                 }
997                         }
998                 }
999         }
1000
1001         /* edge pass */
1002         threshold = (float)cos((angle + 0.00001) * M_PI / 180.0);
1003         for (e=bm->edges.first; e; e=e->next) {
1004                 e->tflag1 = BME_BEVEL_ORIG;
1005                 weight = 0.0;
1006                 /* originally coded, an edge gets tagged with BME_BEVEL_BEVEL in this pass if
1007                  * BME_BEVEL_VERT is not set
1008                  * the edge is manifold (shared by exactly two faces)
1009                  * BME_BEVEL_SELECT is passed and the edge has e->flag&SELECT or
1010                  * BME_BEVEL_EWEIGHT is passed, and the edge has the crease set or
1011                  * BME_BEVEL_ANGLE is passed, and the edge is sharp enough
1012                  * BME_BEVEL_VWEIGHT is passed, and both verts are set for bevel
1013                  */
1014                 /* originally coded, a vertex gets tagged with BME_BEVEL_BEVEL in this pass if
1015                  * the vert belongs to the edge
1016                  * the vert is not tagged with BME_BEVEL_NONMAN
1017                  * the edge is eligible for bevel (even if BME_BEVEL_VERT is set, or the edge is shared by less than 2 faces)
1018                  */
1019                 /* originally coded, a vertex gets a transform weight set in this pass if
1020                  * the vert belongs to the edge
1021                  * the edge has a weight
1022                  */
1023                 /* note: edge weights are cumulative at the verts,
1024                  * i.e. the vert's weight is the average of the weights of its weighted edges
1025                  */
1026
1027                 if (e->loop == NULL) {
1028                         len = 0;
1029                         e->v1->tflag1 |= BME_BEVEL_NONMAN;
1030                         e->v2->tflag1 |= BME_BEVEL_NONMAN;
1031                 }
1032                 else {
1033                         len = BME_cycle_length(&(e->loop->radial));
1034                 }
1035
1036                 if (len > 2) {
1037                         /* non-manifold edge of the worst kind */
1038                         continue;
1039                 }
1040
1041                 if ((options & BME_BEVEL_SELECT) && (e->flag & SELECT)) {
1042                         weight = 1.0;
1043                         /* stupid editmode doesn't always flush selections, or something */
1044                         e->v1->flag |= SELECT;
1045                         e->v2->flag |= SELECT;
1046                 }
1047                 else if ((options & BME_BEVEL_WEIGHT) && (options & BME_BEVEL_VERT) == 0) {
1048                         weight = e->bweight;
1049                 }
1050                 else if (options & BME_BEVEL_ANGLE) {
1051                         if ((e->v1->tflag1 & BME_BEVEL_NONMAN) == 0 && BME_bevel_get_angle(bm,e,e->v1) < threshold) {
1052                                 e->tflag1 |= BME_BEVEL_BEVEL;
1053                                 e->v1->tflag1 |= BME_BEVEL_BEVEL;
1054                                 BME_bevel_add_vweight(td, bm, e->v1, 1.0, 1.0, options);
1055                         }
1056                         else {
1057                                 BME_bevel_add_vweight(td, bm, e->v1, 0.0, 1.0, options);
1058                         }
1059                         if ((e->v2->tflag1 & BME_BEVEL_NONMAN) == 0 && BME_bevel_get_angle(bm,e,e->v2) < threshold) {
1060                                 e->tflag1 |= BME_BEVEL_BEVEL;
1061                                 e->v2->tflag1 |= BME_BEVEL_BEVEL;
1062                                 BME_bevel_add_vweight(td, bm, e->v2, 1.0, 1.0, options);
1063                         }
1064                         else {
1065                                 BME_bevel_add_vweight(td, bm, e->v2, 0.0, 1.0, options);
1066                         }
1067                 }
1068                 //~ else if ((options & BME_BEVEL_VWEIGHT) && (options & BME_BEVEL_VERT) == 0) {
1069                         //~ if ((e->v1->tflag1 & BME_BEVEL_BEVEL) && (e->v2->tflag1 & BME_BEVEL_BEVEL)) {
1070                                 //~ e->tflag1 |= BME_BEVEL_BEVEL;
1071                         //~ }
1072                 //~ }
1073                 else if ((options & BME_BEVEL_SELECT) == 0
1074                         && (options & BME_BEVEL_VERT) == 0)
1075                 {
1076                         weight = 1.0;
1077                 }
1078
1079                 if (weight > 0.0) {
1080                         e->tflag1 |= BME_BEVEL_BEVEL;
1081                         BME_bevel_add_vweight(td, bm, e->v1, weight, 1.0, options);
1082                         BME_bevel_add_vweight(td, bm, e->v2, weight, 1.0, options);
1083                 }
1084
1085                 if (len != 2 || options & BME_BEVEL_VERT) {
1086                         e->tflag1 &= ~BME_BEVEL_BEVEL;
1087                 }
1088         }
1089
1090         /* face pass */
1091         for (f=bm->polys.first; f; f=f->next) f->tflag1 = BME_BEVEL_ORIG;
1092
1093         /*clean up edges with 2 faces that share more than one edge*/
1094         for (e=bm->edges.first; e; e=e->next){
1095                 if(e->tflag1 & BME_BEVEL_BEVEL){
1096                         int count = 0;
1097                         count = BME_face_sharededges(e->loop->f, ((BME_Loop*)e->loop->radial.next->data)->f);
1098                         if(count > 1){
1099                                 e->tflag1 &= ~BME_BEVEL_BEVEL;
1100                         }       
1101                 }
1102         }
1103
1104         return bm;
1105 }
1106
1107 /* tags all elements as originals */
1108 static BME_Mesh *BME_bevel_reinitialize(BME_Mesh *bm) {
1109         BME_Vert *v;
1110         BME_Edge *e;
1111         BME_Poly *f;
1112
1113         for (v = bm->verts.first; v; v=v->next) {
1114                 v->tflag1 |= BME_BEVEL_ORIG;
1115         }
1116
1117         for (e=bm->edges.first; e; e=e->next) {
1118                 e->tflag1 |= BME_BEVEL_ORIG;
1119         }
1120
1121         for (f=bm->polys.first; f; f=f->next) {
1122                 f->tflag1 |= BME_BEVEL_ORIG;
1123         }
1124
1125         return bm;
1126 }
1127
1128 /**
1129  *                      BME_bevel_mesh
1130  *
1131  *      Mesh beveling tool:
1132  *
1133  *      Bevels an entire mesh. It currently uses the tflag1's of
1134  *      its vertices and edges to track topological changes.
1135  *  The parameter "value" is the distance to inset (should be negative).
1136  *  The parameter "options" is not currently used.
1137  *
1138  *      Returns -
1139  *  A BME_Mesh pointer to the BMesh passed as a parameter.
1140 */
1141
1142 static void bmesh_dissolve_disk(BME_Mesh *bm, BME_Vert *v){
1143         BME_Poly *f;
1144         BME_Edge *e;
1145         int done, len;
1146         
1147         if(v->edge){
1148                 done = 0;
1149                 while(!done){
1150                         done = 1;
1151                         e = v->edge; /*loop the edge looking for a edge to dissolve*/
1152                         do{
1153                                 f = NULL;
1154                                 len = BME_cycle_length(&(e->loop->radial));
1155                                 if(len == 2){
1156                                         f = BME_JFKE_safe(bm,e->loop->f, ((BME_Loop*)(e->loop->radial.next->data))->f, e);
1157                                 }
1158                                 if(f){ 
1159                                         done = 0;
1160                                         break;
1161                                 }
1162                                 e = BME_disk_nextedge(e,v);
1163                         }while(e != v->edge);
1164                 }
1165                 BME_collapse_vert(bm, v->edge, v, 1.0);
1166                 //BME_JEKV(bm,v->edge,v);
1167         }
1168 }
1169 static BME_Mesh *BME_bevel_mesh(BME_Mesh *bm, float value, int res, int options, int defgrp_index, BME_TransData_Head *td) {
1170         BME_Vert *v, *nv;
1171         BME_Edge *e, *oe;
1172         BME_Loop *l, *l2;
1173         BME_Poly *f;
1174         unsigned int i, len;
1175
1176         for (f=bm->polys.first; f; f=f->next) {
1177                 if(f->tflag1 & BME_BEVEL_ORIG) {
1178                         BME_bevel_poly(bm,f,value,options,td);
1179                 }
1180         }
1181
1182         /* here we will loop through all the verts to clean up the left over geometry */
1183         /* crazy idea. when res == 0, don't remove the original geometry */
1184         for (v = bm->verts.first; v; /* we may kill v, so increment in-loop */) {
1185                 nv = v->next;
1186                 if ((v->tflag1 & BME_BEVEL_NONMAN) && (v->tflag1 & BME_BEVEL_BEVEL) && (v->tflag1 & BME_BEVEL_ORIG)) {
1187                         v = BME_bevel_wire(bm, v, value, res, options, td);
1188                 }
1189                 else if (res && ((v->tflag1 & BME_BEVEL_BEVEL) && (v->tflag1 & BME_BEVEL_ORIG))) {
1190                         int count = 0;
1191                         /* first, make sure we're not sitting on an edge to be removed */
1192                         oe = v->edge;
1193                         e = BME_disk_nextedge(oe,v);
1194                         while ((e->tflag1 & BME_BEVEL_BEVEL) && (e->tflag1 & BME_BEVEL_ORIG)) {
1195                                 e = BME_disk_nextedge(e,v);
1196                                 if (e == oe) {
1197                                         //printf("Something's wrong! We can't remove every edge here!\n");
1198                                         break;
1199                                 }
1200                         }
1201                         /* look for original edges, and remove them */
1202                         oe = e;
1203                         while ( (e = BME_disk_next_edgeflag(oe, v, 0, BME_BEVEL_ORIG | BME_BEVEL_BEVEL)) ) {
1204                                 count++;
1205                                 /* join the faces (we'll split them later) */
1206                                 f = BME_JFKE_safe(bm,e->loop->f,((BME_Loop*)e->loop->radial.next->data)->f,e);
1207                                 if (!f){
1208                                         //printf("Non-manifold geometry not getting tagged right?\n");
1209                                 }
1210                         }
1211
1212                         /*need to do double check *before* you bevel to make sure that manifold edges are for two faces that share only *one* edge to make sure it doesnt hang here!*/
1213
1214
1215                         /* all original edges marked to be beveled have been removed;
1216                          * now we need to link up the edges for this "corner" */
1217                         len = BME_cycle_length(BME_disk_getpointer(v->edge, v));
1218                         for (i=0,e=v->edge; i < len; i++,e=BME_disk_nextedge(e,v)) {
1219                                 l = e->loop;
1220                                 l2 = l->radial.next->data;
1221                                 if (l->v != v) l = l->next;
1222                                 if (l2->v != v) l2 = l2->next;
1223                                 /* look for faces that have had the original edges removed via JFKE */
1224                                 if (l->f->len > 3) {
1225                                         BME_split_face(bm,l->f,l->next->v,l->prev->v,&l,l->e); /* clip this corner off */
1226                                         if (len > 2) {
1227                                                 l->e->tflag1 |= BME_BEVEL_BEVEL;
1228                                         }
1229                                 }
1230                                 if (l2->f->len > 3) {
1231                                         BME_split_face(bm,l2->f,l2->next->v,l2->prev->v,&l,l2->e); /* clip this corner off */
1232                                         if (len > 2) {
1233                                                 l->e->tflag1 |= BME_BEVEL_BEVEL;
1234                                         }
1235                                 }
1236                         }
1237                         bmesh_dissolve_disk(bm, v);
1238                 }
1239                 v = nv;
1240         }
1241
1242         return bm;
1243 }
1244
1245 static BME_Mesh *BME_tesselate(BME_Mesh *bm) {
1246         BME_Loop *l, *nextloop;
1247         BME_Poly *f;
1248
1249         for (f=bm->polys.first; f; f=f->next) {
1250                 l = f->loopbase;
1251                 while (l->f->len > 4) {
1252                         nextloop = l->next->next->next;
1253                         /* make a quad */
1254                         BME_split_face(bm,l->f,l->v,nextloop->v,NULL,l->e);
1255                         l = nextloop;
1256                 }
1257         }
1258         return bm;
1259 }
1260
1261
1262 /*Main bevel function:
1263         Should be only one exported
1264
1265 */
1266
1267 /* options that can be passed:
1268  * BME_BEVEL_VWEIGHT    <---- v, Look at vertex weights; use defgrp_index if option is present
1269  * BME_BEVEL_SELECT             <---- v,e, check selection for verts and edges
1270  * BME_BEVEL_ANGLE              <---- v,e, don't bevel-tag verts - tag verts per edge
1271  * BME_BEVEL_VERT               <---- e, don't tag edges
1272  * BME_BEVEL_EWEIGHT    <---- e, use crease flag for now
1273  * BME_BEVEL_PERCENT    <---- Will need to think about this one; will probably need to incorporate into actual bevel routine
1274  * BME_BEVEL_RADIUS             <---- Will need to think about this one; will probably need to incorporate into actual bevel routine
1275  * All weights/limits are stored per-vertex
1276  */
1277 BME_Mesh *BME_bevel(BME_Mesh *bm, float value, int res, int options, int defgrp_index, float angle, BME_TransData_Head **rtd) {
1278         BME_Vert *v;
1279         BME_TransData_Head *td;
1280         BME_TransData *vtd;
1281         int i;
1282         float fac=1, d;
1283
1284         td = BME_init_transdata(BLI_MEMARENA_STD_BUFSIZE);
1285
1286         BME_bevel_initialize(bm, options, defgrp_index, angle, td);
1287
1288         /* recursion math courtesy of Martin Poirier (theeth) */
1289         for (i=0; i<res-1; i++) {
1290                 if (i==0) fac += 1.0f/3.0f; else fac += 1.0f/(3 * i * 2.0f);
1291         }
1292         d = 1.0f/fac;
1293         /* crazy idea. if res == 0, don't remove original geometry */
1294         for (i=0; i<res || (res==0 && i==0); i++) {
1295                 if (i != 0) BME_bevel_reinitialize(bm);
1296                 BME_model_begin(bm);
1297                 BME_bevel_mesh(bm,d,res,options,defgrp_index,td);
1298                 BME_model_end(bm);
1299                 if (i==0) d /= 3; else d /= 2;
1300         }
1301
1302         BME_tesselate(bm);
1303
1304         if (rtd) {
1305                 *rtd = td;
1306                 return bm;
1307         }
1308
1309         /* transform pass */
1310         for (v = bm->verts.first; v; v=v->next) {
1311                 if ( (vtd = BME_get_transdata(td, v)) ) {
1312                         if (vtd->max && (*vtd->max > 0 && value > *vtd->max)) {
1313                                 d = *vtd->max;
1314                         }
1315                         else {
1316                                 d = value;
1317                         }
1318                         VECADDFAC(v->co,vtd->org,vtd->vec,vtd->factor*d);
1319                 }
1320                 v->tflag1 = 0;
1321         }
1322
1323         BME_free_transdata(td);
1324         return bm;
1325 }