source/blender/blenkernel/intern/BME_tools.c

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