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