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