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