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