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