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